Prime Number Sieve in Python

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]

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

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.