03-12-2014, 12:44 AM
Code:
a = set(range(2,n+1))
l = round(n**0.5)
for i in range(2,int(l+1)):
if i in a:
s = i**2
while s <= n:
if s in a:
a.remove(s)
s += i
return list(a)
This is O(sqrt n) if I'm not mistaken.