Skip to content

Instantly share code, notes, and snippets.

@scythe
Created February 12, 2012 02:53
Show Gist options
  • Save scythe/1805940 to your computer and use it in GitHub Desktop.
Save scythe/1805940 to your computer and use it in GitHub Desktop.
357
--Solves Project Euler problem 357.
function filltablesieve(lim, qf)
local sievetable = {}
for i = 1, lim do sievetable[i] = false end --use optimized tables
for i = 1, lim do
for j = i, lim / i, 1 do
sievetable[j * i] = sievetable[j*i] or qf(i, j)
end
end
return sievetable
end
function primetest(primetable) --closure uses primetable to test for primality
return function(i, j)
return primetable[i + j]
end
end
primegenerators = filltablesieve(100000000, primetest(filltablesieve(200000000, function(i) return i > 1 end)))
sum = 0
for i = 1, 100000000 do
if not primegenerators[i] then sum = sum + i end
end
print(sum)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment