Re: returning none when it should be returning a list?
- From: "Dave Hughes" <dave@xxxxxxxxxxxxxxxxx>
- Date: 01 May 2006 19:34:25 GMT
Edward Elliott wrote:
randomtalk@xxxxxxxxx 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.
--
.
- References:
- returning none when it should be returning a list?
- From: randomtalk
- Re: returning none when it should be returning a list?
- From: Edward Elliott
- returning none when it should be returning a list?
- Prev by Date: Re: list*list
- Next by Date: How do I take a directory name from a given dir?
- Previous by thread: Re: returning none when it should be returning a list?
- Next by thread: Re: returning none when it should be returning a list?
- Index(es):
Relevant Pages
|
