Last active
May 4, 2016 01:57
-
-
Save BenGoldberg1/9ade3281ab1195a8e49ec84823cc820c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use v6; | |
constant DEBUGGING = False; | |
my class PrimesI does Iterator { | |
has @!primes = (2, 3); | |
has @!sieve = (Any xx 3); | |
has $!p = 3; | |
has $!q = $!p * $!p; | |
has $!n = $!p; | |
method pull-one returns Int { | |
return @!primes.shift if @!primes and @!primes[0] < 4; | |
my $p_ix = 0; | |
for @!sieve.kv -> $offset, $s { | |
$!n += 2; | |
print "n, p and q are $!n, $!p, $!q, sieve is " ~ @!sieve.gist ~ " " if DEBUGGING; | |
if $s { | |
say "Composite" if DEBUGGING; | |
# n is not prime. It's prime factors, uniqified, are @s. | |
@!sieve[ $offset+$_ ].push: $_ for @$s; | |
} elsif ( $!n < $!q ) { | |
say "Prime; sieve is now ", @!sieve if DEBUGGING; | |
# n is prime. | |
@!sieve.splice: 0, $offset+1; | |
@!primes.splice: 0, $p_ix; | |
@!primes.push: $!n; | |
return $!n; | |
} else { | |
# n is equal to q, which in turn is equal to p*p, | |
# which of course is composite. | |
say "Square; primes is " ~ @!primes if DEBUGGING; | |
# Store the next composite after n in the sieve. | |
@!sieve[ $offset+$!p ].push: $!p; | |
$!p = @!primes[ $p_ix++ ]; | |
$!q = $!p*$!p; | |
} | |
}; | |
die "Shouldn't get here!"; | |
}; | |
method is-lazy { True } | |
method count-only { Inf } | |
}; | |
for ^1 { | |
my @res; | |
for Seq.new(PrimesI.new) { | |
last if $_ > 10000000; | |
push @res, $_; | |
}; | |
put "Found {@res.elems} prime numbers."; | |
} | |
note "Took {time - INIT time} seconds"; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment