Prime Sieve of Eratosthenes.py

From Algorithmist
Revision as of 15:16, 14 March 2012 by 70.112.125.148 (Talk)
Jump to: navigation, search

Implementation of the Prime Sieve of Eratosthenes in Python:

from math import sqrt
 
    def FindPrimes(self, limit):
        isPrime = {}
        for i in range(1, limit + 1):
            isPrime[i] = True
 
        isPrime[2] = False
        for i in range(2, int(math.sqrt(limit)) + 1):
            if not isPrime[i]:
                for factor in range(1, limit + 1):
                    j = i * factor
                    if (j > limit): break
                    isPrime[j] = False
 
        isPrime[2] = True
        primes = []
        for i in range(1, limit + 1):
            if isPrime[i]:
                primes.append(i)
 
        return primes
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox