a better prime number generator

Rupendra Dhillon dhillon_rs at rediffmail.com
Sun Oct 21 19:39:42 CEST 2001


hi all,
I have just been introduced to pyton and find it a very good ( takes
off all the bookwork ) language. I was trying to develope a ast prime
number generator. I designed the following algo. Can you please
suggest a faster one or modifications to this only to make it faster

#the following algo returns all the primes below x

def getPrimesTill(x):
	a = range(2,x)
	c = [2]
	
	i = 0
	j = 0

	foundone = 1
	
	while i < len(a):
		while j < len(c) and (c[j] < (.5 * a[i]) ) and foundone == 1:
			if a[i]%c[j] == 0:
				foundone = 0
			j = j + 1
		if foundone == 1 and i > 0:
			c.append(a[i])
		j = 0
		foundone = 1
		i = i + 1
	return c


roop



More information about the Python-list mailing list