105 lines
2.6 KiB
Text
105 lines
2.6 KiB
Text
-- parent script "sieve"
|
|
property _sieve
|
|
|
|
----------------------------------------
|
|
-- @constructor
|
|
----------------------------------------
|
|
on new (me)
|
|
me._sieve = []
|
|
me._primeSieve(100) -- arbitrary initial size of sieve
|
|
return me
|
|
end
|
|
|
|
----------------------------------------
|
|
-- Returns sorted list of first n primes p with p >= a (default: a=1)
|
|
----------------------------------------
|
|
on getNPrimes (me, n, a)
|
|
if voidP(a) then a = 1
|
|
i = a
|
|
res = []
|
|
repeat while TRUE
|
|
if i>me._sieve.count then me._primeSieve(2*i)
|
|
if me._sieve[i] then res.add(i)
|
|
if res.count=n then return res
|
|
i = i +1
|
|
end repeat
|
|
end
|
|
|
|
----------------------------------------
|
|
-- Returns sorted list of primes p with a <= p <= b
|
|
----------------------------------------
|
|
on getPrimesInRange (me, a, b)
|
|
if me._sieve.count<b then me._primeSieve(b)
|
|
primes = []
|
|
repeat with i = a to b
|
|
if me._sieve[i] then primes.add(i)
|
|
end repeat
|
|
return primes
|
|
end
|
|
|
|
----------------------------------------
|
|
-- Returns nth prime
|
|
----------------------------------------
|
|
on getNthPrime (me, n)
|
|
if me._sieve.count<2*n then me._primeSieve(2*n)
|
|
i = 0
|
|
found = 0
|
|
repeat while TRUE
|
|
i = i +1
|
|
if i>me._sieve.count then me._primeSieve(2*i)
|
|
if me._sieve[i] then found=found+1
|
|
if found=n then return i
|
|
end repeat
|
|
end
|
|
|
|
----------------------------------------
|
|
-- Sieve of Eratosthenes
|
|
----------------------------------------
|
|
on _primeSieve (me, limit)
|
|
if me._sieve.count>=limit then
|
|
return
|
|
else if me._sieve.count>0 then
|
|
return me._complementSieve(limit)
|
|
end if
|
|
me._sieve = [0]
|
|
repeat with i = 2 to limit
|
|
me._sieve[i] = 1
|
|
end repeat
|
|
c = sqrt(limit)
|
|
repeat with i = 2 to c
|
|
if (me._sieve[i]=0) then next repeat
|
|
j = i*i
|
|
repeat while (j<=limit)
|
|
me._sieve[j] = 0
|
|
j = j + i
|
|
end repeat
|
|
end repeat
|
|
end
|
|
|
|
----------------------------------------
|
|
-- Expands existing sieve to new limit
|
|
----------------------------------------
|
|
on _complementSieve (me, n)
|
|
n1 = me._sieve.count
|
|
repeat with i = n1+1 to n
|
|
me._sieve[i] = 1
|
|
end repeat
|
|
c1 = sqrt(n1)
|
|
repeat with i = 2 to c1
|
|
if (me._sieve[i]=0) then next repeat
|
|
j = n1 - (n1 mod i)
|
|
repeat while (j<=n)
|
|
me._sieve[j] = 0
|
|
j = j + i
|
|
end repeat
|
|
end repeat
|
|
c = sqrt(n)
|
|
repeat with i = c1+1 to c
|
|
if (me._sieve[i]=0) then next repeat
|
|
j = i*i
|
|
repeat while (j<=n)
|
|
me._sieve[j] = 0
|
|
j = j + i
|
|
end repeat
|
|
end repeat
|
|
end
|