Get this book > Problems on Array: For Interviews and Competitive Programming
In this article, we have designed and implemented a Multithreaded Python code to find Prime Numbers using Sieve of Eratosthenes.
Understand the Time Complexity Analysis of Sieve of Eratosthenes.
Table of Contents
 Introduction
 Code
 Complexity
 Applications
 Questions
 Conclusion
Introduction

Multithreading is a powerful tool that allows programmers to execute multiple tasks concurrently within a single process. In this article, we will explore how to use multithreading in Python to find all prime numbers less than a given number N using the Sieve of Eratosthenes algorithm.

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.
In addition to using the Sieve of Eratosthenes algorithm to find all prime numbers less than a given number N, we can also use other algorithms to find prime numbers in a list of integers. For example, one approach is to define a function that takes a list of integers as an argument and returns a new list containing only the prime numbers from the input list.


The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to a specified integer N. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2.

In a singlethreaded implementation, the algorithm would iterate over each number from 2 to the square root of N, and for each number, mark all its multiples as composite.

In a multithreaded implementation, the range of numbers to be marked can be divided into smaller subranges, and each subrange can be assigned to a separate thread for processing. This way, multiple threads can work on marking multiples of primes concurrently.

In Python, multithreading can be implemented using the threading module. Each thread can be created as an instance of the Thread class and started by calling its start() method. The threads can then run concurrently until they complete their tasks.

Using multithreading in this algorithm can speed up the process of finding all prime numbers less than N by taking advantage of multiple CPU cores to perform computations in parallel.


One way to implement this function is to use a for loop to iterate over each number in the input list and check if it is prime by calling another function that determines if a given number is prime. If the number is prime, it can be appended to the output list.
Hereâ€™s an example of what this function might look like in Python:
def primes_in_list(numbers):
primes = []
for n in numbers:
if is_prime(n):
primes.append(n)
return primes
This approach can be useful when we have a specific list of numbers that we want to check for primality rather than finding all primes less than a given number N.
Code
 Hereâ€™s an example implementation in Python:
from threading import Thread
def sieve_of_eratosthenes(n):
# Create a boolean array "prime[0..n]" and initialize all entries it as true.
# A value in prime[i] will finally be false if i is Not a prime, else true.
primes = [True for _ in range(n + 1)]
p = 2
while p * p<=n:
# If primes[p] is not changed, then it is a prime
if primes[p]:
# Update all multiples of p
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
return [p for p in range(2,n) if primes[p]]
def find_primes(n_threads,n):
threads = []
chunk_size = n // n_threads
for i in range(n_threads):
start = i * chunk_size
end = start + chunk_size if i != n_threads  1 else n
t = Thread(target=sieve_of_eratosthenes,args=(end,))
t.start()
threads.append(t)
for t in threads:
t.join()
if __name__ == '__main__':
find_primes(4,100)
 Letâ€™s break down the code into parts:
 We start by importing the Thread class from the threading module.
from threading import Thread
 Next we define our sieve_of_eratosthenes function which takes an integer n as input and returns a list of all primes less than n.
def sieve_of_eratosthenes(n):
 Inside this function we create an array primes with length n+1 and initialize all its elements to True.
primes = [True for _ in range(n + 1)]
 We also define a variable p which starts at 2 (the first prime number).
p = 2
 We then enter into a while loop which continues until pp<=n. This condition ensures that we only need to check for primes up to the square root of n.
while p * p<=n:
 Inside this loop we check if primes[p] is still set to True (i.e., it hasnâ€™t been marked as composite yet). If it is still True then we know that p must be a prime number.
if primes[p]:
 We then update all multiples of p by setting their corresponding elements in the primes array to False (i.e., marking them as composite).
for i in range(p * p, n + 1, p):
primes[i] = False
 After updating all multiples of p, we increment its value by one and continue with the next iteration of our while loop.
p += 1
 Once our while loop has completed we can return our list of primes by filtering out any elements from our original array which have been marked as False (i.e., they are composite).
return [p for p in range(2,n) if primes[p]]
 Next we define our main function called â€˜find_primesâ€™ which takes two arguments: â€˜n_threadsâ€™ representing number of threads and â€˜nâ€™ representing maximum limit.
def find_primes(n_threads,n):
 Inside our find_primes function we first create an empty list called threads which will store our thread objects.
threads = []
 We also calculate the size of each chunk of data that we will process by dividing n by the number of threads.
chunk_size = n // n_threads
 We then enter into a for loop which iterates over the number of threads.
for i in range(n_threads):
 Inside this loop we calculate the start and end indices for each chunk of data.
start = i * chunk_size
end = start + chunk_size if i != n_threads  1 else n
 We then create a new thread object and pass it our sieve_of_eratosthenes function as its target along with the end index as an argument.
t = Thread(target=sieve_of_eratosthenes,args=(end,))
 We start our thread and add it to our list of threads.
t.start()
threads.append(t)
 After all our threads have been created and started we enter into another for loop which iterates over each thread in our list.
for t in threads:
 Inside this loop we call the join method on each thread which blocks execution until that thread has completed its work.
t.join()
 Finally, we have a conditional statement that checks if this script is being run directly (as opposed to being imported as a module). If it is being run directly then we call our find_primes function with 4 threads and a maximum value of 100.
if __name__ == '__main__':
find_primes(4,100)
Complexity

The time complexity of the Sieve of Eratosthenes algorithm is O(N log log N). By using multithreading, we can further improve the performance of the algorithm by dividing the workload among multiple threads. This allows us to take advantage of multiple CPU cores and process data in parallel.

When analyzing the time complexity of a multithreaded implementation of the Sieve of Eratosthenes algorithm, it is important to include the number of threads p as a parameter. This is because the time complexity of an algorithm can change when it is executed in parallel using multiple threads. For example, if an algorithm has a time complexity of O(N) when executed sequentially on a single thread, its time complexity when executed in parallel using p threads could be O(N/p), assuming that the workload is evenly divided among the threads and there is no overhead from synchronization or communication between threads.

The exact performance improvement will depend on factors such as the number of threads used and the size of the input data. However, itâ€™s important to note that there is a tradeoff between performance and complexity when using multithreading. While it can improve performance, it also adds additional complexity to our code and can make it more difficult to debug and maintain.
Applications

Finding prime numbers has many applications in mathematics and computer science. For example, they are used in cryptography for tasks such as generating secure keys for encryption algorithms. Prime numbers are also used in primality testing which is an important step in many cryptographic protocols.

In addition to their use in cryptography, prime numbers also have many other applications. For example, they are used in hashing algorithms which are commonly used for tasks such as indexing data in databases or searching for items in large datasets.

Prime numbers also have many interesting properties which make them a popular subject of study among mathematicians. For example, they play a key role in number theory and have been studied extensively throughout history.
Questions
 How does multithreading improve performance?
 Can you think of other algorithms that could benefit from multithreading?
 What are some other applications of finding prime numbers?
Conclusion

In this article, we explored how to use multithreading in Python to find all prime numbers less than a given number N using the Sieve of Eratosthenes algorithm. We discussed the time complexity of the algorithm and how multithreading can improve performance by dividing the workload among multiple threads. We also looked at some of the applications of finding prime numbers in fields such as cryptography and computer science.

Overall, multithreading is a powerful tool that can help us improve the performance of our algorithms and solve problems more efficiently. By understanding how to use it effectively we can write better code and tackle more complex challenges.

I hope you found this article informative and useful!