I’m trying to find a better implementation/optimization of Erastosthene’s Sieve for prime numbers.
Here’s my current code. Any spots for improving it? I’m thinking of trying to make a version that only calculates a few per draw(), instead of this brute force all-at-once method.
Also, is there any real separation between an instance method and a static method in LUA? it sure seems like there isn’t…
function Coprime:findAllPrimesBelowP(p)
local _primes = {}
local search = {}
local i
local j
local n
--create our table to search thru
for i = 1, p do
table.insert( search, Coprime( i, true ) )
print( "insert:", search[i]._a, search[i]._b )
end
for i = 2, math.ceil( math.sqrt(p)) do
local cp = search[i]
if( cp._b == true ) then
for n = 0, p do
for j = i^2, p, i*n do
search[j]._b = false
--print( j, search[j]._a, search[j]._b )
end
end
end
end
for i=1, #search do
if( search[i]._b == true ) then
table.insert( _primes, search[i] )
end
end
return _primes
end
You can wrap your function in a coroutine, and yield periodically (say after certain number of comparisons). It could look like this:
Sieve tab
Sieve = class()
function Sieve:findPrimesSmallerThan(n)
-- op-counter: to slice the work into small chunks
local op, MAXOP = 0, 200
return coroutine.create(function()
print("Looking for primes <", n, "...")
self.results = {}
local t = {}
for i=2,n do
t[i] = i
end
local p = 2
while p < n do
if t[p] then
self.lastPrime = p
local x = p * p
while x < n do
t[x] = nil
x = x + p
-- only do a slice of work
op = op + 1
if op % MAXOP == 0 then
coroutine.yield()
end
end
self.results[#self.results + 1] = p
end
p = p + 1
-- only do a slice of work
op = op + 1
if op % MAXOP == 0 then
coroutine.yield()
end
end
print("Prime hunting done.")
return self.results
end)
end
The MAXOPS essentially controls how quickly you want the search to work. Make that value larger - and the routine will work faster, but that may affect your rendering.
Then, in the Main, you’d resume the coroutine continuously, until it’s complete. Adding an animation helps to see if you’re doing too much work in one slice or not: if too many calculations, then the animation becomes choppy, and you may want to decrease MAXOPS.
Main tab
-- Eratosthenes Sieve
-- Use this function to perform your initial setup
function setup()
print("Hello World!")
sieve = Sieve()
co = sieve:findPrimesSmallerThan(10000)
parameter.watch('sieve.lastPrime')
-- setup some animation to happen concurrently
-- with the math
e = {x = 10, y = 400}
tween(5, e, {x=700},
{easing = tween.easing.linear, loop = tween.loop.forever})
end
-- This function gets called once every frame
function draw()
-- This sets a dark background color
background(40, 40, 50)
-- This sets the line thickness
strokeWidth(5)
-- do some prime hunting
if coroutine.status(co) ~= "dead" then
ok, res = coroutine.resume(co)
if not ok then
print("PROBLEM:", res)
elseif res then
print("Found primes:", #res)
end
end
-- some drawing
ellipse(e.x, e.y, 60)
end
Oh, and about class(static) vs instance methods - i think you’re right: the way objects are implemented in Codea, there is no distinction. Personally, i didn’t find any practical need for them, but if you really wanted to, you could create a more sophisticated object model yourself - Lua has all the building blocks for it.
@matkatmusic Here’s an example of the Sieve showing the removal of the multiples of numbers to give the prime numbers up to 1135.
displayMode(FULLSCREEN)
supportedOrientations(LANDSCAPE_ANY)
textMode(CORNER)
rectMode(CORNER)
ellipseMode(CORNER)
fontSize(15)
font("Courier")
backingMode(RETAINED)
function setup()
all=false
done=false
p=2
n=1135
ct=1
x=0
y=1
hx=0
hy=0
a={}
a[1]=0
for z=2,n do
a[z]=1
end
end
function Sieve()
if p*p<=n then
j=p*p
while j<=n do
a[j]=0
j=j+p
end
end
end
function draw()
if hx+hy>0 then
fill(0)
rect(hx*38,HEIGHT-hy*17,38,17)
end
if done and not all then
fill(0)
rect(WIDTH/2,20,500,20)
fill(255)
text("tap screen to remove multiples of "..p,WIDTH/2,20)
return
else
fill(0)
rect(WIDTH/2,20,500,20)
fill(255)
if p>2 then
text("removing multiples of "..rm,WIDTH/2,20)
end
end
if all then
fill(0)
rect(WIDTH/2,20,500,20)
fill(255)
text("Sieve complete",WIDTH/2,20)
return
end
ct=ct+1
str=string.format("%4d",ct)
if a[ct]==0 then
fill(255)
ellipse(x*38,HEIGHT-y*17,10)
hx=x
hy=y
else
fill(255)
text(str,x*38,HEIGHT-y*17)
end
x=x+1
if x>26 then
x=0
y=y+1
if y>42 then
x=0
y=1
ct=1
done=true
end
end
end
function touched(t)
if t.state==ENDED and done then
Sieve()
ct=1
x=0
y=1
rm=p
p=p+1
if p>math.sqrt(n) then
all=true
return
end
while a[p]==0 do
p=p+1
end
done=false
end
end
Just for fun, I was going to link to a question on TeX-SX about displaying the Sieve because it has lots of nice renderings. However, when I checked the question then I saw that I’d actually given an answer with an algorithm in lua for it, so it isn’t “just for fun” (although the algorithm was written for use with LuaLaTeX not Codea).