Basic prime number generator in Python -
just wanted feedback on prime number generator. e.g. ok, use resources etc. uses no libraries, it's simple, , reflection of current state of programming skills, don't hold want learn.
def prime_gen(n): primes = [2] = 2 while < n: counter = 0 in primes: if % == 0: counter += 1 if counter == 0: primes.append(a) else: counter = 0 = + 1 print primes
there few optimizations thar common:
example:
def prime(x): if x in [0, 1]: return false if x == 2: return true n in xrange(3, int(x ** 0.5 + 1)): if x % n == 0: return false return true - cover base cases
- only iterate square root of n
the above example doesn't generate prime numbers tests them. adapt same optimizations code :)
one of more efficient algorithms i've found written in python found in following question ans answer (using sieve):
simple prime generator in python
my own adaptation of sieve algorithm:
from itertools import islice def primes(): if hasattr(primes, "d"): d = primes.d else: primes.d = d = {} def sieve(): q = 2 while true: if q not in d: yield q d[q * q] = [q] else: p in d[q]: d.setdefault(p + q, []).append(p) del d[q] q += 1 return sieve() print list(islice(primes(), 0, 1000000)) on hardware can generate first million primes pretty (given written in python):
prologic@daisy thu apr 23 12:58:37 ~/work/euler $ time python foo.py > primes.txt real 0m19.664s user 0m19.453s sys 0m0.241s prologic@daisy thu apr 23 12:59:01 ~/work/euler $ du -h primes.txt 8.9m primes.txt