returning none when it should be returning a list?

[Dave Hughes]

Edward Elliott wrote:

> 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.

The Prime Number article[1] on Wikipedia has a nice little Python
snippet implementing this algorithm (more or less). See the Finding
Prime Numbers section.

> 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.

Further reading: the Sieve of Eratosthenes[2] is a relatively simple
and fun little algorithm to implement (also has a size issue in that it
requires a list of numbers from 2 up to the largest number you wish to
test for primality, and I don't think it's any faster than the
algorithm above). A modern refinement called the Sieve of Atkin[3] is
also interesting, a bit faster, although rather more complicated.

If you want to look further into the subject, see the Primality Test
article[4] on Wikipedia (mentions things like probabilistic testing,
the Miller-Rabin primality test, and such like).

[1] http://en.wikipedia.org/wiki/Prime_number
[2] http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
[3] http://en.wikipedia.org/wiki/Sieve_of_Atkin
[4] http://en.wikipedia.org/wiki/Primality_test


Dave.
--