Optimalization of the primes finding function

Question

After 10 minutes of work I have written a function presented below. It returns a list of all primes lower than an argument. I have used all known for me programing and mathematical tricks in order to make this function as fast as possible. To find all the primes lower than a million it takes about 2 seconds.

Do you see any possibilities to optimize it even further? Any ideas?

def Primes(To):
  if To<2:
    return []
  if To<3:
    return [2]
  Found=[2]
  n=3
  LastSqr=0
  while n<=To:
     k=0
     Limit=len(Found)
     IsPrime=True
     while k<Limit:
         if k>=LastSqr: 
            if Found[k]>pow(n,0.5): 
               LastSqr=k
               break
         if n%Found[k]==0:
            IsPrime=False
            break
         k+=1
     if IsPrime:
        Found.append(n)
     n+=1
  return Found

http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python — jsalter, Jul 31 '12 at 13:48
A quick test with timeit confirms, `sqrt(n)` is indeed faster than `pow(n,0.5)` — mgilson, Jul 31 '12 at 13:57
calculating `sqrt(n)` or `pow(n, 0.5)` before `while k < Limit` will be better as it gets calculated once for every pair of (n, k), while you only need to calculate it once for every n. — Mahmoud Aladdin, Jul 31 '12 at 14:05
@user1354439 Please have a look at [PEP 8](http://www.python.org/dev/peps/pep-0008/) concerning the names of identifiers such as local variables. — glglgl, Jul 31 '12 at 14:05

Max · Accepted Answer · 2012-08-03T13:27:08.383

You can use a couple tricks to speed things up, using the basic sieve of erastothenes. One is to use Wheel Factorization to skip calculating numbers that are known not to be prime. For example, besides 2 and 3, all primes are congruent to 1 or 5 mod 6. This means you don't have to process 4 of every 6 numbers at all.

At the next level, all primes are congruent to 1, 7, 11, 13, 17, 19, 23, or 29, mod 30. You can throw out 22 of every 30 numbers.

Here is a simple implementation of the sieve of Erastothenes that doesn't calculate or store even numbers:

def basic_gen_primes(n):
    """Return a list of all primes less then or equal to n"""
    if n < 2:
        return []

    # The sieve.  Each entry i represents (2i + 1)
    size = (n + 1) // 2
    sieve = [True] * size

    # 2(0) + 1 == 1 is not prime
    sieve[0] = False

    for i, value in enumerate(sieve):
        if not value:
            continue

        p = 2*i + 1

        # p is prime.  Remove all of its multiples from the sieve
        # p^2 == (2i + 1)(2i + 1) == (4i^2 + 4i + 1) == 2(2i^2 + 2i) + 1
        multiple = 2 * i * i + 2 * i 
        if multiple >= size:
            break

        while multiple < size:
            sieve[multiple] = False
            multiple += p 

    return [2] + [2*i+1 for i, value in enumerate(sieve) if value]

As mentioned, you can use more exotic sieves as well.

the fact deserves ***stressing*** that your code here is the ***sieve of Eratosthenes***, and so should always be much faster than a trial division code like that of OP, when implemented correctly. — Will Ness, Aug 03 '12 at 09:41

score 4 · Answer 2 · answered Jul 31 '12 at 13:44

4

You can check only odd numbers. So why don't you use n+=2 instead of n+=1?

answered Jul 31 '12 at 13:44

user1365836

330
3
12

Good idea :) I will check if it has shortened the time of execution, Thank you – Piotr Dabkowski Jul 31 '12 at 13:46
Incrementing by six and checking `n-1` and `n+1` in each iteration might be faster still. It's a common trick to optimize the Sieve of Eratosthenes by skipping over the multiples of three as well. (Never tried it in Python, though.) – Fred Foo Jul 31 '12 at 13:54

score 2 · Answer 3 · answered Jul 31 '12 at 13:41

google and wikipedia for better algorithms. If you are only looking for small primes this might be fast enough. But the real algorithms are a lot faster for large primes.

http://en.wikipedia.org/wiki/Quadratic_sieve

start with that page.

Increment n by two instead of one. ?

Optimalization of the primes finding function

3 Answers3