Skip to content

Instantly share code, notes, and snippets.

@Veedrac
Last active August 2, 2017 20:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Veedrac/bea3a17296151ff860788120ee0aff1a to your computer and use it in GitHub Desktop.
Save Veedrac/bea3a17296151ff860788120ee0aff1a to your computer and use it in GitHub Desktop.
def genPrimes(n):
found = []
found_lo = []
for x in range(2,n+1):
yas = True
for y in found_lo:
if x%y == 0:
yas = False
break
if yas:
found.append(x)
if x <= n**0.5:
found_lo.append(x)
return found
def genPrimes_set(n):
found = []
found_lo = set()
for x in range(2,n+1):
yas = True
for y in found_lo:
if x%y == 0:
yas = False
break
if yas:
found.append(x)
if x <= n**0.5:
found_lo.add(x)
return found
import timeit
print(min(timeit.Timer(lambda: genPrimes(1000000)).repeat(10, 1)))
print(min(timeit.Timer(lambda: genPrimes_set(1000000)).repeat(10, 1)))
#>>> 1.1185914840025362
#>>> 1.354676898001344
def primes_raw(n):
result = set(range(2, n + 1))
div = 2
while div * div <= n:
if div in result:
result.difference_update(range(div * 2, n + 1, div))
div += 1
return sorted(result)
def primes_raw_lst(n):
result = [True] * (n + 1)
result[0] = result[1] = False
div = 2
while div * div <= n:
if result[div]:
for x in range(div * 2, n + 1, div):
result[x] = False
div += 1
return result
def primes_raw_lst_fast(n):
result = [True] * (n + 1)
result[0] = result[1] = False
div = 2
while div * div <= n:
if result[div]:
result[div * 2::div] = [0] * len(range(div * 2, n + 1, div))
div += 1
return result
import timeit
print(min(timeit.Timer(lambda: primes_raw(1000000)).repeat(10, 10)))
print(min(timeit.Timer(lambda: primes_raw_lst(1000000)).repeat(10, 10)))
print(min(timeit.Timer(lambda: primes_raw_lst_fast(1000000)).repeat(10, 10)))
#>>> 2.0144221499940613
#>>> 1.204771492004511
#>>> 0.23468445800244808
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment