How to Check if Numbers are Prime Concurrently in Python

Last Updated on September 12, 2022

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:

How to check factors for prime numbers one-by-one in Python and how slow it can be.
How to use the ProcessPoolExecutor to manage a pool of worker processes.
How to use the ProcessPoolExecutor to check for prime numbers concurrently.

Let’s dive in.

Table of Contents

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:

If the number is less than 2, not prime.
If the number is 2, prime.
If the number can be divided by 2 with no remainder, not prime.
If the number has a divisor between 3 and sqrt(n), not prime
Otherwise, prime.

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

Run loops using all CPUs, download your FREE book to learn how.

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[i]} 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:

Built-in Functions

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

Download Now: Free ProcessPoolExecutor PDF Cheat Sheet

Extensions

This section lists ideas for extending the tutorial.

Test Numbers From 1 to 1,000. Update the example to test a large range of numbers with the is_prime() function to confirm it is working correctly, such as all numbers between 1 and 1,000.
Test Primality For Larger Numbers. Update the example to test larger numbers and report how long it takes to complete both serially and concurrently.
Share Divisors Across Workers. Update the example to test one very large number for primality and share divisors to check across multiple workers.

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

Free Python ProcessPoolExecutor Course

Download your FREE ProcessPoolExecutor PDF cheat sheet and get BONUS access to my free 7-day crash course on the ProcessPoolExecutor API.

Discover how to use the ProcessPoolExecutor class including how to configure the number of workers and how to execute tasks asynchronously.

Learn more

Takeaways

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

How to check factors for prime numbers one-by-one in Python and how slow it can be.
How to use the ProcessPoolExecutor to manage a pool of worker processes.
How to use the ProcessPoolExecutor to check for prime numbers concurrently.

Do you have any questions?
Leave your question in a comment below and I will reply fast with my best advice.

Photo by Andrew Palmer on Unsplash