1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
-- This is the (naive) Sieve of Eratosthenes. Public domain.
local bit = require("bit")
local band, bxor, rshift, rol = bit.band, bit.bxor, bit.rshift, bit.rol
local function nsieve(p, m)
local count = 0
for i=0,rshift(m, 5) do p[i] = -1 end
for i=2,m do
if band(rshift(p[rshift(i, 5)], i), 1) ~= 0 then
count = count + 1
for j=i+i,m,i do
local jx = rshift(j, 5)
p[jx] = band(p[jx], rol(-2, j))
end
end
end
return count
end
if arg and arg[1] then
local N = tonumber(arg[1]) or 1
if N < 2 then N = 2 end
local primes = {}
for i=0,2 do
local m = (2^(N-i))*10000
io.write(string.format("Primes up to %8d %8d\n", m, nsieve(primes, m)))
end
else
assert(nsieve({}, 10000) == 1229)
end
|
