Created
July 30, 2013 18:51
-
-
Save sunu/6115704 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# N is the range in which you find all primes | |
N = 10000 | |
# initialize an array of flags | |
is_prime = [1 for num in xrange(N)] | |
is_prime[0] = 0 # this is because indexing starts at zero | |
is_prime[1] = 0 # one is not a prime, but don't mark all of its multiples! | |
def set_prime(num): | |
"num is a prime; set all of its multiples in is_prime to zero" | |
for x in xrange(num*2, N, num): | |
is_prime[x] = 0 | |
# iterate over all integers up to N and update the is_prime array accordingly | |
for num in xrange(N): | |
if is_prime[num] == 1: | |
set_prime(num) | |
primes = [num for num in xrange(N) if is_prime[num]] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment