Multiprocessing in Python to find prime numbers

Question

In Python 3 I have this assignment where I need to find prime numbers in a interval [a,b] using multiprocessing.

Let's take as an example the interval [0,30] and with the use of 3 processes I have three intervals [ai,bi] : [0.10] ,[10,20] , [20,30]

Here is my code:

import multiprocessing
import time
def isprime(num):
  if num > 1:
       for i in range(2, num):
            if (num % i) != 0:
               pass
       else:
           return num

if __name__ == "__main__":
    pool = multiprocessing.Pool(3)
    start_time = time.perf_counter()
    result = pool.map(isprime, range(0,30))
    finish_time = time.perf_counter()
    print(f"Program finished in {finish_time-start_time} seconds")
    print(result)

   

This is the outpot expected:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

This is what I get:

[None, None, 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]

Answer 1

You have three problems:

1. Your isprime function will implicitly return None for arguments <= 1 but otherwise will always execute the else clause of your for statement and return the passed argument.
2. On the assumption that isprime will return the passed argument if it is prime or None if it is not, then you need to filter out None returned values from isprime.
3. You didn't actually solve the problem by breaking up the interval into ranges as you indicated was going to be your approach. I will address this in my comments following the code.

import multiprocessing
import time

def isprime(num):
    if num < 2:
        return None
    for i in range(2, num):
         if (num % i) == 0:
            return None
    else:
        return num

if __name__ == "__main__":
    pool = multiprocessing.Pool(3)
    start_time = time.perf_counter()
    result = list(filter(lambda x: x is not None, pool.map(isprime, range(0,30))))
    finish_time = time.perf_counter()
    print(f"Program finished in {finish_time-start_time} seconds")
    print(result)

Prints:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

General Comments

Your isprime function could be greatly improved (do a Google for a better implementations). For example:

def isprime(num):
    from math import sqrt, floor

    if num < 2: return None
    if num == 2: return num
    if num % 2 == 0: return None
    for d in range(3, floor(sqrt(num)) + 1, 2):
        if num % d == 0: return None
    return num

But as you see, as the argument n increases the more iterations of the main loop are required to prove that the passed argument is prime.

The way you could handle this problem is to implement some version of the Sieve of Eraosthenes algorithm, which is efficient in producing a series of prime numbers and you would then pass to this function a range of numbers between which the sieve function would return all the primes it found within that range. You would, of course, break up your initial range(0, 30) into a list of 3 subranges, i.e. [range(0, 10), range(10, 20), range(20, 30)], which would be passed to your map method.

But even the standard Sieve algorithm must start generating primes starting with 2 so even when you pass the argument range(10, 20) to it, the function would have to duplicate work that is being done when the argument range(0, 10) is being passed.

So using multiple calls to a isprime method is not efficient for finding a range of primes but a Sieve algorithm gains nothing from a multiprocessing implementation (multiprocessing actually hurts performance). The best way to solve this problem would be with a non-multiprocessing Sieve.