diff options
| -rwxr-xr-x | challenge-168/steve-g-lynn/perl/ch-2.pl | 29 |
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; + |