Re: returning none when it should be returning a list?

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.

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.

.

Relevant Pages

  • Re: no lcm in standard library?
    ... which are comparable to the AMD K6 architecture, branch misprediction ... mispredict penalties tilt the algorithm choice in favor of Euclid's ... This implements the binary GCD algorithm which removes the branch ... that it approximates the divide as a 1-bit accurate divide, ...
    (comp.lang.c)
  • Re: rules of fixed-point arithmetic
    ... divide to keep everything fast. ... or you could even use one of the old bit shift divide ... used a good old bit shift algorithm. ... rather than table lookup, perhaps with simple correction factors / ...
    (comp.arch)
  • Re: can multi-core improve single funciton?
    ... divide: fib, fib ... def fib: ... versus millions of years for the OP's algorithm. ...
    (comp.lang.python)
  • Re: returning none when it should be returning a list?
    ... It divide next by the list of previous ... Your basic algorithm as described above sounds workable, ... the Sieve of Eratosthenesis a relatively simple ... If you want to look further into the subject, see the Primality Test ...
    (comp.lang.python)
  • Re: prime number routine
    ... > need a routine for figuring out if a number inputted by the user is a prime ... If it is bigger than your max, then you have to start doing ... bigger than the square root of the number. ... And you don't need to divide by any number that is itself ...
    (comp.lang.cpp)