Merge pull request #6238 from steve-g-lynn/new-branch

New branch

1 files changed, 21 insertions, 8 deletions

diff --git a/challenge-168/steve-g-lynn/perl/ch-2.pl b/challenge-168/steve-g-lynn/perl/ch-2.pl
index d1f6f0aced..5fe95544ad 100755
--- a/challenge-168/steve-g-lynn/perl/ch-2.pl
+++ b/challenge-168/steve-g-lynn/perl/ch-2.pl
@@ -1,13 +1,19 @@
 #!/usr/bin/perl
 
-use Math::Prime::XS qw(is_prime sieve_primes);
+use Math::Prime::XS qw(is_prime);
 
+print &home_prime(10),"\n";
+#773
 
 print &home_prime(16),"\n";
-#-- should be 31636373 [wikipedia example]
+#31636373
+
+print &home_prime(20),"\n";
+#3318308475676071413
 
 sub home_prime {
-	local ($n)=@_;
+	my ($n)=@_;
+	is_prime($n) && return $n;
 	while (1){
 		$n=&factors($n);
 		(is_prime($n)) && last;
@@ -15,23 +21,30 @@ sub home_prime {
 	return $n;
 }
 
-
 sub factors {
 	#--return concatenated prime factors of a number n 
-	local ($n)=@_;
-	local @primes=sieve_primes($n);
-	local $retstring="";
+	my ($n)=@_;
+	local $sqrt_n=floor(sqrt($n));
+
+	my $retstring="";
 	
 	if (is_prime($n)){
 		return $n;
 	}
 	else {
-		foreach $prime (sort{$a<=>$b} @primes){
+		for $prime (2 .. $sqrt_n){
+		#-- no need to get primes first
+		#-- routine automatically finds only prime factors
 			while ( ($n % $prime) == 0){
 				$n /= $prime;
 				$retstring .= $prime;
 			}
+			(is_prime($n)) && last; 
 		}
+		($n > 1) && ($retstring .= $n);
 	}
 	return $retstring;	
 }
+
+1;
+