31 lines
1.2 KiB
Plaintext
31 lines
1.2 KiB
Plaintext
// http://stackoverflow.com/revisions/10733621/4
|
|
|
|
fcn postponed_sieve(){ # postponed sieve, by Will Ness
|
|
vm.yield(2); vm.yield(3); # original code David Eppstein,
|
|
vm.yield(5); vm.yield(7); # ActiveState Recipe 2002
|
|
D:=Dictionary();
|
|
ps:=Utils.Generator(postponed_sieve); # a separate Primes Supply:
|
|
p:=ps.pump(2,Void); # (3) a Prime to add to dict
|
|
q:=p*p; # (9) when its sQuare is
|
|
c:=9; # the next Candidate
|
|
while(1){
|
|
if (not D.holds(c)){ # not a multiple of any prime seen so far:
|
|
if (c < q) vm.yield(c); # a prime, or
|
|
else{ # (c==q): # the next prime's square:
|
|
add(D,c + 2*p,2*p); # (9+6,6 : 15,21,27,33,...)
|
|
p=ps.next(); # (5)
|
|
q=p*p; # (25)
|
|
}
|
|
}else{ # 'c' is a composite:
|
|
s := D.pop(c); # step of increment
|
|
add(D,c + s,s); # next multiple, same step
|
|
}
|
|
c += 2; # next odd candidate
|
|
}
|
|
}
|
|
|
|
fcn add(D,x,s){ # make no multiple keys in Dict
|
|
while(D.holds(x)){ x += s } # increment by the given step
|
|
D[x] = s;
|
|
}
|