Welcome, guest | Sign In | My Account | Store | Cart

Generate all prime numbers up to n.

Python, 21 lines
 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()

4 comments

Rui Ferreira 15 years, 2 months ago  # | flag

These are not sieves

dth (author) 15 years, 2 months ago  # | flag

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.

hasanatkazmi 15 years, 2 months ago  # | flag

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

Thomas Ahle 14 years, 5 months ago  # | flag

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]
Created by dth on Tue, 3 Feb 2009 (MIT)
Python recipes (4591)
dth's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks