Making A Program Multithreaded

I'm making a prime number calculator, It works perfectally, but I want it to be faster through the use of multithreading. I was wondering if any of you could point me to somewhere

Solution 1:

The most popular implementations of Python (CPython and PyPy) come with a Global Interpreter Lock ("GIL"). The purpose of this is basically to simplify memory management. The effect of it is that only one thread at a time can be executing Python bytecode. So for a program that does all its calculations in Python, threading won't make it faster.

Usually the best was to make a program faster is to find a better algorithm. Look e.g. at this:

def prime_list(num):
    """Returns a list of all prime numbers up to and including num.

    :num: highest number to test
    :returns: a list of primes up to num

    """
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2)  # (1)
    L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))]  #(2)
    return [2] + L  # (3)

(1) Even numbers >2 can be divided by two, so they cannot be prime and need not be considered.

(2): For an odd number c to be prime, one must ensure that c modulo all previous odd numbers (p) must be non-zero.

(3): 2 is also a prime number.

A small improvement is that p only needs to go up to sqrt(c).

def prime_list2(num):
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2)
    L = [c for c in candidates if all(c % p != 0 for p in
         range(3, int(math.sqrt(c))+1, 2))]
    return [2] + L

Note that I'm using list comprehensions instead of for-loops, because they are generally faster.

Finally, a kind of sieve as Adam Smith mentioned;

def prime_list3(num):
    num += 1
    candidates = range(3, num, 2)
    results = [2]
    while len(candidates):
        t = candidates[0]
        results.append(t)
        candidates = [i for i in candidates if not i in range(t, num, t)]
    return results

To see which one is faster, we need to run tests;

First for num=100.

In [8]: %timeit prime_list(100)
1000 loops, best of 3: 185 µs per loop

In [9]:  %timeit prime_list2(100)
10000 loops, best of 3: 156 µs per loop

In [10]: %timeit prime_list3(100)
1000 loops, best of 3: 313 µs per loop

Then 1000:

In [11]: %timeit prime_list(1000)
100 loops, best of 3: 8.67 ms per loop

In [12]: %timeit prime_list2(1000)
1000 loops, best of 3: 1.94 ms per loop

In [13]: %timeit prime_list3(1000)
10 loops, best of 3: 21.6 ms per loop

Then 10000;

In [14]: %timeit prime_list(10000)
1 loops, best of 3: 680 ms per loop

In [15]: %timeit prime_list2(10000)
10 loops, best of 3: 25.7 ms per loop

In [16]: %timeit prime_list3(10000)
1 loops, best of 3: 1.99 s per loop

Of these algoriths, prime_list2 seems to hold up best.