Prime Sieve of Eratosthenes.py
From Algorithmist
Revision as of 15:16, 14 March 2012 by 70.112.125.148 (Talk)
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