A question.

[Jeff Epler]

On Tue, 12 Dec 2000 12:32:09 +0100, DeHa
 <deha at poczta.onet.pl> wrote:
>Hi All!

Hello!

Are you trying to implement the algorithm known as the 'sieve of Eratosthenes'?

Here is my implementation:

def sieve(max = 1000):
	# elements of r correspond to numbers, 0 means the number has been
	# proved composite, 1 means the number is a suspected prime
	r = [1] * (max+1)

	# The list of numbers to return
	p = []

	# Look at each number in turn
	for i in range(2, max+1):

		# If it is already known to be composite, do nothing
		if not r[i]: continue

		# If it is suspected prime, and all divisors have been
		# tested, then it is known to be prime
		p.append(i)

		# Mark all multiples of the number as composite
		# eg range(2*3, 1001, 3) -> (6, 9, 12, ..., 999)
		for j in range(2*i, max+1, i):
			r[j] = 0

	# We have tested all candidates, so p contains the list of
	# all primes less than or equal to max
	return p

assert sieve(30) = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]