returning none when it should be returning a list?

[Edward Elliott]

randomtalk at gmail.com wrote:
> The function basically takes in a list of all the prime number found,
> it takes the next number to be tested for (next) and the limit it will
> go up to. It divide next by the list of previous prime numbers if next
> is not bigger than lim, count up all the times where it's not evenly
> divdided, if the result is equal the length of prime number, then we
> have another prime number, lather rinse and repeat :)

Your basic algorithm as described above sounds workable, but can be made
more efficient (I didn't look closely at your code for bugs).  I won't even
go near the complicated number theory algorithms.

1. integer mod will be faster than floating point mod (unless you're getting
into numbers too large to store efficiently as ints, but you'll probably
run into other limitations before you get near that point in this code).

2. you can stop as soon as you find a zero remainder, no need to keep
testing the rest of the primes in the list.

3. you can stop testing numbers at the halfway point.  there are no primes
smaller than 2, so no number x can have a factor larger than x/2.

4. in fact you can do even better.  a simple proof by contradiction shows
that if primes 1..y don't divide x and y^2 > x then x must be prime.  put
another way, once you test up to the square root of x, there's no point
continuing.  if one factor were bigger than sqrt(x), the other would have
to be smaller than sqrt(x).  but you've already tested the factors smaller
than sqrt(x), so there can't be any factors.

5. you can do better than checking every odd number (next+2) to find the
next prime, but I'm too tired to look into it right now.  it may require
more complex machinery.

Locating primes is an interesting challenge because of the seemingly endless
grades of refinements over simple brute-force search.  Like I said though,
if speed and size aren't concerns, your algorithm is fine.