Engineers, scientists, and financial analysts frequently use optimization methods to solve computationally expensive problems such as simulation of complex systems, high-dimensional data analysis, or data compression. Algorithm optimization can dramatically improve computational performance—even by one or two orders of magnitude. One effective optimization method is parallel computing. To fully benefit from parallelization, it is crucial to choose an approach appropriate for the specific computational problem.

Finding prime numbers is a popular educational programming problem. Typically, this task is solved using traditional sequential programming. In this tutorial, we will demonstrate that computation time can be significantly reduced by using multiple processes working simultaneously. The solution is implemented in Python.

There are important considerations when using parallelization. The most critical issue is translating a sequential problem into a parallel one. At first glance, finding prime numbers appears to be an iterative task that requires fetching a number, checking if it is prime using the isprime function, then moving to the next number, and so on. However, we can observe that numbers do not need to be processed in sequential order—they can be handled in any order, meaning computations for each number can be performed independently. This insight can be translated into an algorithm that divides the initial sequence of numbers into separate sets, each of which can be processed independently by a worker.

But how many sets (and thus workers) should we use? The number of effective workers or processes depends on the number of physical cores in the computer's processor. Generally, no performance improvements are seen once the number of processes exceeds the number of physical CPU cores (unless the system has multiple CPUs). In our code, we assume 4 processes, fixed by a CORE constant. While this is a conservative assumption (most modern CPUs have more than 4 cores), it is sufficient for demonstration purposes.

The code consists of a main block and two supporting functions: isprime, which checks if a number is prime, and sum_primes, which counts prime numbers. The sum_primes function serves two purposes: it provides a simple validation for both single-process and multiprocess scenarios implemented in the main code, and it is the core function executed independently by each spawned process. For parallelization, we use Python's multiprocessing package, which offers both local and remote concurrency using subprocesses instead of threads. This allows full utilization of multiple processors on a single machine.

After spawning the processes, each performs computations on its assigned set of numbers. The main process uses process.wait() to wait for all workers to complete their tasks. Results are shared through an array accessible to all processes, assuming shared memory availability.

#SEO Parallelization can dramatically improve algorithm efficiency. In this tutorial, we present an example of parallelizing Python code to increase the speed of prime number computation.