Skip to content

Instantly share code, notes, and snippets.

@nyango
Forked from graph226/prime.py
Last active July 17, 2016 10:06
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 nyango/fcb2651ddc893903d487176bd14bea3f to your computer and use it in GitHub Desktop.
Save nyango/fcb2651ddc893903d487176bd14bea3f to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes by Python
import math
NUMBER = 100000000
def get_prime_list(limit):
limit_sqrt = int(math.ceil(math.sqrt(limit)))
prime_bool_list = [False] * 2 + [True] * (limit - 2)
for prime_cand in xrange(2,limit_sqrt):
if prime_bool_list[prime_cand]:
for composite in range(prime_cand ** 2, limit, prime_cand):
prime_bool_list[composite] = False
return [i for i, b in enumerate(prime_bool_list) if b]
get_prime_list(NUMBER)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment