Making a Program Multithreaded

Question

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 with some resources (the python docs are not very helpful) or give me an example in my code.

import time
#Set variables
check2 = 0
check3 = 0
check5 = 0
check7 = 0
#get number
primenum = int(input("What number do you want to find out whether it is prime or not?\nIt must be a natural number\n**Calculations may take some time depending of the power of the computer and the size of the number**\n"))
#set divisor
primediv = primenum - 2
#assume it's prime until proven innocent
prime = 1
#Create variable for GUI
working = "Calculating"
work = 10000000
#set the number of divides to 0
divnum = 0
#start the clock
starttime = time.perf_counter()
#until it is not prime or divided by 1...
while prime == 1 and primediv >7:
    #does simple checks to deal with large numbers quickly
    #Does this by dividing with small numbers first
    if primenum != 0 and check2 == 0:
        primemod = primenum % 2
        check2 = 1
        print(working + ".")
        working = working +"."
    elif primenum != 0 and check3 == 0:
        primemod = primenum % 3
        check3 = 1
        print(working + ".")
        working = working +"."
    elif primenum != 0 and check5 == 0:
        primemod = primenum % 5
        check5 = 1
        print(working + ".")
        working = working + "."
    elif primenum != 0 and check7 == 0:
        primemod = primenum % 7
        check7 = 1
        print(working + ".")
        working = working + "."
    #divde and get remainder
    else:
        primemod = primenum % primediv
        #Working visuals
        if divnum == work:
            print(working + ".")
            working = working +"."
            work = work + 10000000
    #if the can't be devided evenly
    if primemod == 0:
        #then it isn't a prime
        prime = 0
    else:
        #if it can, keep going
        primediv = primediv - 2
        divnum = divnum + 1
#print results
if prime == 1:
    print("That number is prime")
    print ("It took ", time.perf_counter()-starttime, " seconds to perform that calculation\n")
else:
    print("That number is not prime")
    print ("It took ", time.perf_counter()-starttime, " seconds to perform that calculation\n")

Answer 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.