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:

1 2 3 |
# 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:

1 2 3 4 5 |
# 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.

1 2 3 |
# 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:

1 2 3 4 5 |
# 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:

1 2 3 4 5 |
# 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.

1 2 3 |
... # 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.

1 2 3 |
... # 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# 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.

1 2 3 4 5 6 |
# 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.

1 2 3 4 5 6 |
# 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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.

1 2 3 4 5 6 |
... # 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
# 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?**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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.

1 2 3 4 5 |
... # 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:

1 2 3 4 5 |
... # 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.

1 2 3 4 |
... # 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.

1 2 3 |
... # 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.

1 2 3 4 5 |
... # 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
# 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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.

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

## Further Reading

This section lists helpful additional resources on the topic.

### APIs

### References

## 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

## Do you have any questions?