Entry

Sieves

Jul 5th, 2000 09:59
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 41, Mike Fletcher

"""
Packages: maths.sieves
"""

"""
Hoist the if p > sq inside the test for null, then use a hacky test for
"0"-ness.
"""

def mcfsieve3(n):
	candidates = range(3, n+1, 2)
	sq = int(n**0.5)
	end = ((n+1)-3)/2
	for p in candidates:
		if p is not 0: # cheating :)
			if p > sq:
				break
			for q in xrange(((p*p)-3)/2, end, p):\
				candidates[q] = 0
	candidates = filter(None, candidates)
	candidates.insert(0, 2)
	return candidates