CODEWITHSUNDEEP
pythonperformance
Majid
Majid

Reputation: 261

Find next prime

I am looking for a fast and memory efficient way to find the next prime.

Input: An integer n

Output The first prime bigger then n

There is really nice code to print all primes smaller than n at Fastest way to list all primes below N . My inefficient method currently finds all primes smaller than 2n and then searches for the first prime bigger than n by just looping through the list. Here is my current code.

import numpy
def primesfrom2to(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = numpy.ones(n/3 + (n%6==2), dtype=numpy.bool)
    for i in xrange(1,int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[       k*k/3     ::2*k] = False
            sieve[k*(k-2*(i&1)+4)/3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]

n=10**7
timeit next(x for x in primesfrom2to(2*n) if x > n)
1 loops, best of 3: 2.18 s per loop

n= 10**8
timeit next(x for x in primesfrom2to(2*n) if x > n)
1 loops, best of 3: 21.7 s per loop

This last test takes almost 1GB of RAM. Another problem with this code is that it just fails if $n = 10**10$ for example.

Can this problem be solved faster? Is there a way to get it to use less memory?

Upvotes: 1

Views: 6729

Answers (3)

Majid
Majid

Reputation: 261

The best way to do is apparently as follows.

  1. Start a sieve at n until 2n to eliminate numbers with small primes.
  2. Run a probabilistic prime number tester such as Miller-Rabin on the remaining values.
  3. If needed, run a deterministic prime tester on the first number that has been reported prime.

Upvotes: 2

dmg
dmg

Reputation: 7706

I can think of two ways of going around this. The first one I've tried recently - I made quite an efficient Sieve of Eratosthenes in C++ and made it into a C/C++ Extension for Python.

It's memory efficient as it uses a bitmap instead of an actual array of ints and it's quite fast - for up to 10**9 it works for around 20s on a beat-up one core virtual machine (along with exporting the bitmap to actual ints). In your case you can keep only the bitmap and if you now the absolute max of n you can precompute the primes.

Another approach is to look into some Primality tests, but don't forget that some of them are probabilistic.

Upvotes: 1

Thomas Thorogood
Thomas Thorogood

Reputation: 2357

I'd definitely recommend some sort of sieve or filter.

While trying to solve a problem involving primes for funsies, I created the following in Python: https://gist.github.com/anonymous/4960155

I am able to get through a couple million primes in about 15 seconds, IIRC. It was a little while back. I'm glad I saved it!

Upvotes: 1

Related Questions