SuperFastPython

How to Check if Numbers are Prime Concurrently in Python

February 9, 2022 Python ProcessPoolExecutor

The ProcessPoolExecutor class in Python can be used to check if multiple numbers are prime at the same time.

This can dramatically speed-up your program compared to checking if numbers are prime, one-by-one.

In this tutorial, you will discover how to check if numbers are prime concurrently using a pool of worker processes.

After completing this tutorial, you will know:

Let's dive in.

How to Check if Numbers are Prime One at a Time (slowly)

A prime number is a positive integer that is only divisible by itself and one.

If a number is not prime, it means there are at least one other set of divisors for the number and we might refer to the number technically as "composite".

Prime numbers are a fascinating area of math, but we also can make practical use of them, such as in cryptography (e.g. public and private keys), calculating checksums, configuring hash tables, random number generators and much more.

Given a number, we cannot know if it is prime or not without testing whether it has any divisors besides itself and one. There are many clever algorithms for speeding-up this process, but fundamentally, testing numbers for primality is a manual and slow process.

As such, it makes a good case for exploring how to make programs concurrent using the ProcessPoolExecutor in Python.

It's even used as a small example in the ProcessPoolExecutor API documentation.

Let's get started.

Primality Testing in Python

A number is prime if it is positive and only divisible by itself and one.

The Wikipedia page for primality test lays out a naive algorithm that we can use to test if a number is prime.

The steps can be summarized as follows:

Let's take a closer look at these checks.

Firstly, we can check if a target number is divisible by another number with no remainder by using the modulo operator.

Recall that this operator returns the remainder of a division.

For example, we can check if a number is divisible with no remainder as follows:

# check if divisible with no remainder
def is_divisible(target, number):
	return target % number == 0

To test if a number is prime, we can see if it is divisible by all numbers between 2 and itself minus one with no remainder.

For example:

# check if a target is divisible
for i in range(2, target):
	if target % i == 0:
		# not prime
# otherwise prime

In fact, we can just check if the number is divisible by 2 with no remainder and skip all positive numbers because they too are all divisible by 2.

# check if divisible by 2, rule out all even divisors
if target % 2 == 0:
	# not prime

This leaves only the odd numbers between 3 and the number minus one.

Recall, the range() function will take a step size as a third parameter, therefore we can write something like:

# check if a target is divisible
for i in range(3, target, 2):
	if target % i == 0:
		# not prime
# otherwise prime

When looking at divisors for a number, we see symmetry between [1 to n/2] and [n/2 to n], where n is the number we are considering.

We can push this further according to Wikipedia, and only consider divisors between 3 and the square root of the target, e.g. math.sqrt(target).

We might be able to write something like:

# check if a target is divisible
for i in range(3, sqrt(target), 2):
	if target % i == 0:
		# not prime
# otherwise prime

So far so good.

A minor issue is that the square root may not result in an integer, therefore we need to round it in some way.

We can take the math.floor() of the number which will just keep the integer and drop any fractional values.

...
# calculate the upper limit on divisors to check
limit = floor(sqrt(target))

Finally, we actually want to check the integer that is the square root of the target, not top at one minus this value, which is the default behavior of range(). Therefore, we can add one to this upper limit of divisors to check.

...
# limit on divisors we test, sqrt of n, +1 so range() will reach it
limit = floor(sqrt(number)) + 1

And that's about it.

Tying all of this together, the is_prime() function below will take a number and return True if it is prime or False otherwise.

It's not the fastest algorithm for primality testing, but it will work.

# returns True if prime, False otherwise
def is_prime(number):
    # 1 is a special case of not prime
    if number <= 1:
        return False
    # 2 is a special case of a prime
    if number == 2:
        return True
    # check if the number divides by 2 with no remainder
    if number % 2 == 0:
        return False
    # limit on divisors we test, sqrt of n, +1 so range() will reach it
    limit = floor(sqrt(number)) + 1
    # check for evenly divisible for odd numbers between 3 and sqrt(n)
    for i in range(3, limit, 2):
        # check if number is divisible with no remainder
        if number % i == 0:
            # number is divisible and is not a prime
            return False
    # number is probably prime
    return True

Test Primality for a Series of Numbers

We can now test out our function on some candidate primes.

Let's define a function check_numbers_are_prime() that takes a list of numbers and tests each in turn, reporting if they are prime, and ignoring them if not.

This is a typical use case, where we are interested in what numbers are prime, not whether a given number is prime or not.

The function is listed below.

# check if a series of numbers are prime or not
def check_numbers_are_prime(numbers):
    # check each number in turn
    for number in numbers:
        if is_prime(number):
            print(f'{number} is prime')

Next, let's test it out on some known primes.

The Wikipedia page List of prime numbers provides many lists of prime numbers that we can use for testing.

Importantly, it has a list of all prime numbers between 1 and 1,000.

Let's run 1 throw 100 through our prime testing function and confirm that it can detect them.

Let's call our check_numbers_are_prime() function with a list of all integers between 1 and 100 from the program entry point.

# entry point
if __name__ == '__main__':
    # define some numbers to check
    NUMBERS = list(range(1,101))
    # check whether each number is a prime
    check_numbers_are_prime(NUMBERS)

Tying this together, the complete example is listed below.

# SuperFastPython.com
# report all primes between 1 and 100
from math import sqrt
from math import floor

# returns True if prime, False otherwise
def is_prime(number):
    # 1 is a special case of not prime
    if number <= 1:
        return False
    # 2 is a special case of a prime
    if number == 2:
        return True
    # check if the number divides by 2 with no remainder
    if number % 2 == 0:
        return False
    # limit on divisors we test, sqrt of n, +1 so range() will reach it
    limit = floor(sqrt(number)) + 1
    # check for evenly divisible for odd numbers between 3 and sqrt(n)
    for i in range(3, limit, 2):
        # check if number is divisible with no remainder
        if number % i == 0:
            # number is divisible and is not a prime
            return False
    # number is probably prime
    return True

# check if a series of numbers are prime or not
def check_numbers_are_prime(numbers):
    # check each number in turn
    for number in numbers:
        if is_prime(number):
            print(f'{number} is prime')

# entry point
if __name__ == '__main__':
    # define some numbers to check
    NUMBERS = list(range(1,101))
    # check whether each number is a prime
    check_numbers_are_prime(NUMBERS)

Running the example zips through numbers 1 to 100 and tests each for primality.

Candidate numbers are then reported.

If we check this list against the list on the Wikipedia page, we can confirm that all of the numbers that were reported are prime, and that no non-prime numbers were reported.

So far so good.

Experiment with different number ranges, when does it start to get slow?
Let me know in the comments below, I'd love to hear what you discover.

2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime
53 is prime
59 is prime
61 is prime
67 is prime
71 is prime
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime

Next, let's take a look at testing some very large numbers that are very slow.

Testing Very Large Numbers for Primality

Testing small numbers like those between 1 and 100 or even 1 and 1000 is very fast.

Testing all divisors using our naive algorithm for large algorithms is slow and gets worse as the numbers get larger.

For example, a number like 489133282872437279 (which is prime, taken from the Wikipedia article) has about 350 million factors to test and may take a minute to run on modern hardware.

Ouch.

Let's consider testing a dozen examples of such large numbers.

We can take these numbers from the Wikipedia page that lists some very large prime numbers. We can also spice up the list with variations of known primes that are not primes, e.g. remove, add, or change a digit.

Below is a list of 17 candidate primes we can test, 14 of which are actually prime.

...
# define some numbers to check
NUMBERS = [17977, 10619863, 106198, 6620830889, 80630964769, 228204732751,
    1171432692373, 1398341745571, 10963707205259, 15285151248481,
    99999199999, 304250263527209, 30425026352720, 10657331232548839,
    10657331232548830,  44560482149, 1746860020068409]

The complete example with this updated list of numbers to check for primality is listed below.

# SuperFastPython.com
# check if large numbers are prime
from math import sqrt
from math import floor

# returns True if prime, False otherwise
def is_prime(number):
    # 1 is a special case of not prime
    if number <= 1:
        return False
    # 2 is a special case of a prime
    if number == 2:
        return True
    # check if the number divides by 2 with no remainder
    if number % 2 == 0:
        return False
    # limit on divisors we test, sqrt of n, +1 so range() will reach it
    limit = floor(sqrt(number)) + 1
    # check for evenly divisible for odd numbers between 3 and sqrt(n)
    for i in range(3, limit, 2):
        # check if number is divisible with no remainder
        if number % i == 0:
            # number is divisible and is not a prime
            return False
    # number is probably prime
    return True

# check if a series of numbers are prime or not
def check_numbers_are_prime(numbers):
    # check each number in turn
    for number in numbers:
        if is_prime(number):
            print(f'{number} is prime')
        else:
            print(f'{number} is not prime')

# entry point
if __name__ == '__main__':
    # define some numbers to check
    NUMBERS = [17977, 10619863, 106198, 6620830889, 80630964769, 228204732751,
        1171432692373, 1398341745571, 10963707205259, 15285151248481,
        99999199999, 304250263527209, 30425026352720, 10657331232548839,
        10657331232548830,  44560482149, 1746860020068409]
    # check whether each number is a prime
    check_numbers_are_prime(NUMBERS)

Running the example tests if each number is prime.

We can see that the 14 primes are identified correctly.

Importantly, the process is relatively slow, taking about 7.1 seconds on modern hardware.

This will get progressively worse as we add more large numbers or numbers even larger.

How long did the example take to run on your system?

17977 is prime
10619863 is prime
6620830889 is prime
80630964769 is prime
228204732751 is prime
1171432692373 is prime
1398341745571 is prime
10963707205259 is prime
15285151248481 is prime
99999199999 is prime
304250263527209 is prime
10657331232548839 is prime
44560482149 is prime
1746860020068409 is prime

How to Check if Multiple Numbers are Prime Concurrently

We can update our primality checking program to use the ProcessPoolExecutor directly with very little change.

For example, each call to the is_prime() function could be submitted as an asynchronous task to the process pool.

This means that the overall task could not be completed faster than the slowest task, but it can potentially be much faster than the serial case above if most tasks are fast to complete, e.g. modestly sized numbers like those we are testing.

If we were testing numbers significantly larger, we might need to use an alternate strategy.

For example, rather than testing one number as a parallel task, we can split the divisors for each number up into tasks in order to reduce the time to test each number. This might introduce difficulty in shutting down all tasks once non primality was established.

Nevertheless, we have two options for submitting calls to is_prime() into the process pool: we could use submit() or map().

Using submit() would allow us to report results as they became available using as_completed(), whereas map() would require us to report results in the order that numbers are submitted to the pool.

The is_prime() function returns a True or False value for a number only. Both submit() and map() require a way to associate the result of the task with the number that was submitted.

In the case of using submit() we can create a mapping of Future objects to submitted numbers.

In the case of map() we can iterate the list of numbers in the same order that was passed to map().

For example, we could use the built-in enumerate() function on the results from map() to get an index and use that to reference numbers that were submitted.

...
# check if numbers are prime
for i,result in map(is_prime, numbers):
	if result:
		print(f'{numbers} is prime')

Perhaps a simpler approach is to use the built-in zip() function to iterate the results from map() and the list of numbers at the same time, for example:

...
# check if numbers are prime
for number, result in zip(numbers, map(is_prime, numbers)):
    if result:
        print(f'{number} is prime')

If you are new to the enumerate() and zip() built-in functions see:

The map() function feels like a better fit in this case as we are simply applying a function to a list of items, exactly what map() is designed to achieve.

Let's update our check_numbers_are_prime() function to use the ProcessPoolExecutor.

First, we can create the process pool using the context manager with the default number of workers.

...
# create process pool
with ProcessPoolExecutor() as executor:
    # ...

We can then dispatch the tasks to the process pool using map(), one call to is_prime() for each number in the list.

As there are less than 20 tasks, we don't need to tune the "chunksize" argument to map() to get better performance. This might be required if we have thousands or millions of items in the list.

...
# submit the tasks
results = executor.map(is_prime, numbers)

We can then iterate a zip() of the numbers and results of calling is_prime() for each number and report primality.

...
# report results in order
for number, isprime in zip(numbers, results):
    if isprime:
        print(f'{number} is prime')

Tying this together, the updated version of checking numbers for primality concurrently using the ProcessPoolExecutor is listed below.

# SuperFastPython.com
# check if large numbers are prime concurrently
from math import sqrt
from math import floor
from concurrent.futures import ProcessPoolExecutor

# returns True if prime, False otherwise
def is_prime(number):
    # 1 is a special case of not prime
    if number <= 1:
        return False
    # 2 is a special case of a prime
    if number == 2:
        return True
    # check if the number divides by 2 with no remainder
    if number % 2 == 0:
        return False
    # limit on divisors we test, sqrt of n, +1 so range() will reach it
    limit = floor(sqrt(number)) + 1
    # check for evenly divisible for odd numbers between 3 and sqrt(n)
    for i in range(3, limit, 2):
        # check if number is divisible with no remainder
        if number % i == 0:
            # number is divisible and is not a prime
            return False
    # number is probably prime
    return True

# check if a series of numbers are prime or not
def check_numbers_are_prime(numbers):
    # create process pool
    with ProcessPoolExecutor() as executor:
        # submit the tasks
        results = executor.map(is_prime, numbers)
        # report results in order
        for number, isprime in zip(numbers, results):
            if isprime:
                print(f'{number} is prime')

# entry point
if __name__ == '__main__':
    # define some numbers to check
    NUMBERS = [17977, 10619863, 106198, 6620830889, 80630964769, 228204732751,
        1171432692373, 1398341745571, 10963707205259, 15285151248481,
        99999199999, 304250263527209, 30425026352720, 10657331232548839,
        10657331232548830,  44560482149, 1746860020068409]
    # check whether each number is a prime
    check_numbers_are_prime(NUMBERS)

Running the example tests the list of numbers for primality as we did before.

We see the same results, which is as expected.

In this case, the program finishes in about half the time or about 4.7 seconds on my system. That is about a 1.5x speedup.

How much speedup did you achieve on your system?
Let me know in the comments below.

17977 is prime
10619863 is prime
6620830889 is prime
80630964769 is prime
228204732751 is prime
1171432692373 is prime
1398341745571 is prime
10963707205259 is prime
15285151248481 is prime
99999199999 is prime
304250263527209 is prime
10657331232548839 is prime
44560482149 is prime
1746860020068409 is prime

Extensions

This section lists ideas for extending the tutorial.

Share your extensions in the comments below, it would be great to see what you come up with.

Takeaways

In this tutorial you discovered how to check if numbers are prime concurrently using a pool of worker processes.



If you enjoyed this tutorial, you will love my book: Python ProcessPoolExecutor Jump-Start. It covers everything you need to master the topic with hands-on examples and clear explanations.