47 lines
1.4 KiB
Text
47 lines
1.4 KiB
Text
with javascript_semantics
|
|
sequence primes = {2,3,5,7}
|
|
atom sieved = 10
|
|
|
|
procedure add_block()
|
|
integer N = min((sieved-1)*sieved,400000)
|
|
sequence sieve = repeat(1,N) -- sieve[i] is really i+sieved
|
|
for i=2 to length(primes) do -- (evens filtered on output)
|
|
atom p = primes[i], p2 = p*p
|
|
if p2>sieved+N then exit end if
|
|
if p2<sieved+1 then
|
|
p2 += ceil((sieved+1-p2)/p)*p
|
|
end if
|
|
p2 -= sieved
|
|
if and_bits(p2,1)=0 then p2 += p end if
|
|
-- if sieve[p2] then -- dang!
|
|
for k=p2 to N by p*2 do
|
|
sieve[k] = 0
|
|
end for
|
|
-- end if
|
|
end for
|
|
for i=1 to N by 2 do
|
|
if sieve[i] then
|
|
primes &= i+sieved
|
|
end if
|
|
end for
|
|
sieved += N
|
|
end procedure
|
|
|
|
atom t0 = time()
|
|
while sieved<8000 do add_block() end while
|
|
printf(1,"The first 20 primes are: %v\n",{primes[1..20]})
|
|
integer lo = abs(binary_search(100,primes)),
|
|
hi = abs(binary_search(150,primes))-1
|
|
printf(1,"The primes between 100 and 150 are: %v\n",{primes[lo..hi]})
|
|
lo = abs(binary_search(7700,primes))
|
|
hi = abs(binary_search(8000,primes))
|
|
printf(1,"There are %d primes between 7700 and 8000.\n",hi-lo)
|
|
for i=1 to iff(platform()=JS?7:8) do
|
|
integer k = power(10,i)
|
|
while length(primes)<k do
|
|
add_block()
|
|
end while
|
|
printf(1,"The %,dth prime is : %d\n",{k,primes[k]})
|
|
end for
|
|
?elapsed(time()-t0)
|
|
wait_key()
|