From 0944ad393dfe0e1144825df3a03296da42ef20cc Mon Sep 17 00:00:00 2001 From: James Smith Date: Sun, 6 Feb 2022 18:22:23 +0000 Subject: Update README.md --- challenge-150/james-smith/README.md | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) diff --git a/challenge-150/james-smith/README.md b/challenge-150/james-smith/README.md index 1e048774b7..dcbadeb488 100644 --- a/challenge-150/james-smith/README.md +++ b/challenge-150/james-smith/README.md @@ -70,3 +70,34 @@ say for grep{my$t=$_;!grep{!($t%$_)}@p2}1..$N; ``` **Note** `say` without any parameters - outputs the contents of `$_` and then sends a carriage return. so `say for @A;` outputs all elements of the array `@A` on separate lines. + +## Follow up + +We can re-write the inefficient double `grep` more elegantly with nested `for`*each* loops. The new code becomes: + +```perl +my ( $N, @p2, @r ) = ( @ARGV ? $ARGV[0] : 500 , 4 ); + +P: for ( my $c = 3; $c*$c <= $N; $c += 2 ) { + $_ > $c ? last : $c*$c % $_ || next P for @p2; + push @p2, $c*$c; +} + +O: for my $t ( 1 .. $N ) { + $_ > $t ? last : $t % $_ || next O for @p2; + say $t; +} +``` + +### Notes: + * We optimize the inner loop by allowing it to finish early if: + * We have a prime^2 value greater than `$t` + * We have a square factor + + * The difference in these two cases are: + * We end the inner loop and output the number as a square-free int (`last`) + * We skip to the next iteration of the outer loop (`next O`) without doing anything + + * The optimized version gives anywhere between 75% and 90% speed up... (values of `$N` between 100 and 1,000,000) + + * We have also re-written the prime generator to use the same `next {label}` trick, and this leads to a certain symmetry between the two loops. -- cgit