ActiveState Code

Recipe 576640: Prime Number Generator

Generate all prime numbers up to n.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python

def prime(n):
	"""
	Generate all prime numbers less than n.
	"""
	yield 2
	primes = []
	for m in range(3,n,2):
		if all(m%p for p in primes):
			primes.append(m)
			yield m

def main():
	print list(prime(1000))

	#or a slower one-liner
	print [n for n in range(3,1000,2) if all(n%p for p in range(3,n,2))]

if __name__=="__main__":
	main()

Comments

  1. 1. At 3:07 p.m. on 3 feb 2009, Rui Ferreira said:

    These are not sieves

  2. 2. At 3:29 p.m. on 3 feb 2009, dth (the author) said:

    sieve: (verb) to filter a set of elements based on certain criteria

    It is NOT the Sieve of Eratosthene, and I apologize for mistagging; but it is indeed a sieve nonetheless.

  3. 3. At 12:02 a.m. on 12 feb 2009, hasanatkazmi said:

    This is sieves.

    def getprimes(limit): toreturn = [] numbers = [] for i in range(limit): numbers.append(True) for i in range(2, limit): if numbers[i] == True: toreturn.append(i) numbers[i] = False for j in range(i, limit, i): numbers[j] = False return toreturn

  4. 4. At 10:04 a.m. on 10 nov 2009, Thomas Ahle said:

    A python onliner Sieve:

    >>> primes = lambda l: l and l[:1]+primes(filter(l[0].__rmod__,l))
>>> primes(range(2,40))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Sign in to comment