Prime Number Sieve in Python

Feb, 18, 2017

This program computes all the prime numbers up to 10,000 using an efficient algorithm.

Instead of checking if a number n is prime by dividing by all previous numbers, or even all previous primes, this program only divides by all previous primes less than or equal to the square root of n.

from __future__ import division, print_function

primes = [2]
print(2)

for n in range(3, 10001):
    i, k = 0, 0
    while primes[i] <= n**(1/2):    # No need to check against ALL smaller primes
        if n % primes[i] == 0:      # Check if divisible by previous primes
            k = 1
        i += 1
    if k == 0:                      # If good, at it to the list and print it
        primes.append(n)
        print(n)
Posted in Python | Leave a comment

Leave a Reply

Your email address will not be published. Required fields are marked *

Follow

Get every new post on this blog delivered to your Inbox.

Join other followers: