Edward Elliott wrote: > [EMAIL PROTECTED] 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. -- -- http://mail.python.org/mailman/listinfo/python-list
