Skip to content

Instantly share code, notes, and snippets.

@lapointexavier
Created April 21, 2015 21:37
Show Gist options
  • Save lapointexavier/941d033ea7bc9808a83c to your computer and use it in GitHub Desktop.
Save lapointexavier/941d033ea7bc9808a83c to your computer and use it in GitHub Desktop.
Find Primes Number within a certain limit using the sieve of eratosthenes
import sys
import math
def find_primes(max_number):
is_composite = range(0, max_number + 1)
for i in range(4, max_number, 2):
is_composite[i] = True
next_prime = 3
stop_at = math.sqrt(max_number)
while next_prime <= stop_at:
for i in range(next_prime * 2, max_number, next_prime):
is_composite[i] = True
next_prime = next_prime + 2
while next_prime <= max_number and is_composite[next_prime] == True:
next_prime = next_prime + 2
primes = []
for i in range(2, max_number):
if is_composite[i] != True:
primes.append(i)
print(primes)
return primes
def main():
find_primes(int(sys.argv[1]))
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment