diff options
| -rw-r--r-- | challenge-159/james-smith/perl/ch-2.pl | 53 |
1 files changed, 46 insertions, 7 deletions
diff --git a/challenge-159/james-smith/perl/ch-2.pl b/challenge-159/james-smith/perl/ch-2.pl index 5c86128a4d..7d22c8df6d 100644 --- a/challenge-159/james-smith/perl/ch-2.pl +++ b/challenge-159/james-smith/perl/ch-2.pl @@ -13,26 +13,65 @@ my @TESTS = ( [ 5, -1 ], [ 10, 1 ], [ 20, 0 ], +## The following are good examples where the second algorithm works well! + [ 2, -1 ], + [ 6, 1 ], + [ 30, -1 ], + [ 210, 1 ], + [ 2310, -1 ], + [ 30030, 1 ], + [ 510510, -1 ], + [ 9699690, 1 ], + [ 6895531, -1 ], + [ 206865930, 1 ], + [ 223092870, -1 ], + [ 6469693230, 1 ], ); -is( moebius( $_->[0]), $_->[1] ) foreach @TESTS; -is( moebius_exp($_->[0]), $_->[1] ) foreach @TESTS; +warn "exp"; +is( moebius_exp( $_->[0] ), $_->[1] ) for @TESTS; +warn "opt"; +is( moebius_div_opt( $_->[0] ), $_->[1] ) for @TESTS; +timethis( 500_000, sub { moebius_div_opt( $_->[0] ) for @TESTS } ); +warn "div"; +is( moebius_div( $_->[0] ), $_->[1] ) for @TESTS; +timethis( 100, sub { moebius_div( $_->[0] ) for @TESTS } ); +warn "dumb"; +is( moebius( $_->[0] ), $_->[1] ) for @TESTS; +timethis( 5, sub { moebius( $_->[0] ) for @TESTS } ); done_testing(); sub moebius { my ($n,$p,$r) = (shift,1,1); return -1 if is_prime($n); - $n%($p**2) ? ($n%$p && ($r=-$r)) : return 0 while ($p = next_prime $p) < $n; + $n%($p**2) ? ($n%$p || ($r=-$r)) : return 0 while ($p = next_prime $p) <= $n; + $r; +} + +sub moebius_div { + my ($n,$p,$r) = (shift,1,1); + return -1 if is_prime $n; + $n%($p**2) ? ( $n%$p || ($r=-$r,$n/=$p)) : return 0 while ($p = next_prime $p) && $n>1; + $r; +} + +sub moebius_div_opt { + my ($n,$p,$r) = (shift,1,1); + return -1 if is_prime $n; + $n%$p || ($r=-$r,$n/=$p) && ( $n%$p ? ( (is_prime $n) && (return -$r) ) : return 0 ) while ($p = next_prime $p)**2 <= $n; $r; } sub moebius_exp { my ($n,$p,$r) = (shift,1,1); - return -1 if is_prime($n); - while( ($p = next_prime $p ) < $n ) { - return 0 unless $n%($p**2); - $r=-$r unless $n%$p; + return -1 if is_prime $n; + while( ($p = next_prime $p )**2 <= $n ) { + next if $n%$p; + $r=-$r; + $n/=$p; + return 0 unless $n%$p; + return -$r if is_prime $n; } $r; } |