a better prime number generator

[sburrious]

dhillon_rs at rediffmail.com (Rupendra Dhillon) wrote in message news:<23d58b26.0110210939.55bb7e0c at posting.google.com>...
> #the following algo returns all the primes below x

Not quite.  When I ran your code, it included 4 in the list of primes.
 See below for the reason.

> 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:
                                  ^^^^^^^^^^^^^^^^^^
The culprit is here.  When you get to a[i] == 4 and then test c[j] ==
2, you drop out of the second while loop without checking whether 2 is
a factor of 4.  So "foundone" remains 1, and 4 is identified as prime.

As you've probably noticed from the other responses, you could
eliminate this problem by testing odd numbers only, which is in any
case more efficient.  It's also more efficient to test c[j] <=
math.sqrt(a[i]) rather than .5 * a[i], since the square root of a
number is its largest possible factor.

I have a stylistic objection to your use of the name "foundone"; it's
somewhat misleading, since you don't know if you've "found one" (i.e.
a prime) until you get to the end of the inner loop.

> 			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

Rather than using an index and a while loop to test each member of a,
the more natural approach in Python is to apply a for loop directly to
a.  See below for an example.

> 	return c

Since the other responses have focussed on alternative algorithms, I
thought it might be helpful for you to see an edited version of yours
reflecting the above comments:

import math

def getPrimesTill(x):
    a = range(3, x, 2)   # test odd numbers only, 
    c = [2]              #    since we know 2 is only even prime
    for candidate in a:
        maybeprime = 1
        j = 0
        while (j < len(c) and 
               c[j] <= math.sqrt(candidate) and 
               maybeprime):
            if candidate % c[j] == 0:
                maybeprime = 0
            j += 1
        if maybeprime: c.append(candidate)
    return c