Making my program faster using with compiling

Question

I've made a sieve for generating primes. I'm doing a school project about RSA which includes some programming. I'll use the primes for an RSA system, but because it's for my essay the security isn't really important. However, big primes are much more challenging and I like that. The code I use:

def Zeef(a):
    import math
    upperBound = a
    upperBoundSquareRoot = int(math.sqrt(upperBound))
    isPrime = [1 for m in range (0,upperBound+1)]
    for m in range(2,upperBoundSquareRoot+1):
        if (isPrime[m]==1):
            for k in range(m*m,upperBound+1,m):
                isPrime[k] = 0;
    print("Priemgetallen : ")
    numberofPrimes = 0
    for m in range(2,upperBound+1):
        if (isPrime[m] ==1):
            print(m)
            numberofPrimes = numberofPrimes+1
    print("Aantal = " , numberofPrimes);
a=input("Alle priemgetallen tot: ")
aa=int(a)
Priemen = Zeef(aa)

I'm sure there is a faster way for generating primes, but i'm not really interested in improving my code right now.

When I'm running this function, it works fine for generating primes up to 7 digits, but when I want more, it's really slow. My computer (8gb ram) gives a message that there's not enough memory. I used the same algoritm in Processing, an other tool. Processing is really quick, but it doesn't recognize more than 10 digits. I also noticed the printing is slow when I'm generating primes which my computer is able to calculate.

I began searching on the internet and i found that i compiling my program would speed up the progress, but i'm not sure if it speeds up the calculation and printing part or just the interpreting part. I also found something about numpy wich was about arrays, but I'm not sure if this will notably speeds up my function.

How can I find my primes faster?

Answer 1

You will need a better algorithm than the Sieve of Eratosthenes if you want to generate the kinds of large prime numbers needed for the RSA algorithm. Here's an implementation of the Miller-Rabin primality checker for Python:

def isPrime(n):
    def isSpsp(n, a):
        d, s = n - 1, 0
        while d % 2 == 0: d, s = d / 2, s + 1
        t = pow(a, d, n)
        if t == 1: return True
        while s > 0:
            if t == n - 1: return True
            t, s = (t * t) % n, s - 1
        return False
    ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
         43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    if n in ps: return True
    for p in ps:
        if not isSpsp(n, p): return False
    return True

If you're interested in programming with prime numbers, I modestly recommend this essay at my blog; you might also look at some of the other pages at my blog, including this one on generating RSA semi-primes.

Answer 2

Here's an unoptimized version of your Sieve of Erathostenes, using numpy. On my 8GB laptop running 64 bit versions of Python (2.7) and Numpy (1.7), it computes the prime factors up to 10^9 in under a minute:

import numpy as np

def sieve(a):
    upper_bound = np.int(np.sqrt(a))
    is_prime = np.ones((a+1,), dtype=np.bool)
    for m in xrange(2, upper_bound+1):
        if is_prime[m]:
            is_prime[m*m::m] = False
    return np.where(is_prime)[0][2:]

>>> sieve(100)
array([ 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
       61, 67, 71, 73, 79, 83, 89, 97], dtype=int64)

And here are my timings:

%timeit sieve(10**9)
1 loops, best of 3: 33.4 s per loop

%timeit sieve(10**8)
1 loops, best of 3: 2.47 s per loop

%timeit sieve(10**7)
1 loops, best of 3: 207 ms per loop

%timeit sieve(10**6)
100 loops, best of 3: 7.47 ms per loop

%timeit sieve(10**5)
1000 loops, best of 3: 716 us per loop

You could make it run about twice as fast by removing all the even numbers from the sieve, but even with that and all the memory in the world, you are still looking at several minutes to get all the primes up to 10^10.

Answer 3

You're talking about an issue of computational complexity. There comes a point, with certain problems, where you will be unable to speed up your algorithm no matter how fast your processor or compiler is. For example, if you were trying to solve an NP-complete problem, it would be easy for small values, but hard for larger values.

I recommend you improve your code, even if you don't want to. Or, find a library that handles prime generation on its own. Here is an interesting link: http://rebrained.com/?p=458

That seems to be pretty good code for generating primes...but it doesn't generate large primes either (I tried it on my very fast iMac). It was quick up to about 100000. I recommend looking at this SO question for insights into how to test a randomly generated large number for primality.