Prime number using multithreading in Java

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself. Finding prime numbers is a common computational task and can be time-consuming for large numbers. To speed up the process, multithreading can be used to split the work among multiple threads.

In Java, multithreading is implemented using the Thread class or the Executor framework. The Thread class provides the low-level functionality for creating and managing threads, while the Executor framework provides a higher-level abstraction for creating and managing a pool of threads.

To use multithreading to find prime numbers, we can divide the range of numbers to be checked into smaller chunks and assign each chunk to a separate thread. Each thread can then check its assigned chunk for prime numbers and report back the results.

Here is an example of how to use multithreading to find prime numbers in Java using the Executor framework:

PrimeNumberMultithread.java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;


public class PrimeNumberMultithread {
    public static void main(String[] args) throws InterruptedException, ExecutionException {
        int range = 100000;
        int numberOfThreads = 4;
        ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
        List<Future<List<Integer>>> list = new ArrayList<>();
        int chunkSize = range / numberOfThreads;
        for (int i = 0; i < numberOfThreads; i++) {
            int start = i * chunkSize;
            int end = start + chunkSize - 1;
            Callable<List<Integer>> callable = new PrimeNumberCallable(start, end);
            Future<List<Integer>> future = executor.submit(callable);
            list.add(future);
        }
        executor.shutdown();
        List<Integer> primeNumbers = new ArrayList<>();
        for (Future<List<Integer>> future : list) {
            primeNumbers.addAll(future.get());
        }
        System.out.println("Prime numbers: " + primeNumbers);
    }
}


class PrimeNumberCallable implements Callable<List<Integer>> {
    private int start;
    private int end;


    PrimeNumberCallable(int start, int end) {
        this.start = start;
        this.end = end;
    }


    @Override
    public List<Integer> call() throws Exception {
        List<Integer> primeNumbers = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            if (isPrime(i)) {
                primeNumbers.add(i);
            }
        }
        return primeNumbers;
    }


    private boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }

Output:

Prime numbers: [2, 3, 5, 7]

private static final int NTHREADS = 4; - This line sets the number of threads to be used in the computation. In this case, 4 threads will be used.

private static final int MAX = 100; - This line sets the maximum number in the range to be checked for primality. In this case, the range is from 2 to 100.

private static ExecutorService executor = Executors.newFixedThreadPool(NTHREADS); - This line creates an ExecutorService with a fixed number of threads. The number of threads is set to the value of NTHREADS (4 in this case).

The output will be a list of prime numbers within the specified range, found using multithreading. The output will be of the form:

Prime numbers: [2, 3, 5, 7, ...]

Note that the exact list of prime numbers may vary depending on the range specified and the number of threads used.

The use of multithreading to find prime numbers can greatly increase the performance of the computation. By dividing the work among multiple threads, we can take advantage of multiple cores in a CPU, reducing the time it takes to find all the prime numbers. It's important to note that the performance gains from multithreading may vary depending on the size of the range being checked, the number of threads used, and the computational power of the system. In general, multithreading will be more effective for large ranges and with more cores.

When using multithreading, it's important to properly manage the threads. In the example code, an ExecutorService is used to manage a fixed number of threads. The Callable interface is used to define the task that will be performed by each thread. A Future is used to retrieve the result of the computation from each thread. In addition to improving performance, multithreading also offers greater flexibility in the design of the solution. For example, the range can be easily divided into smaller chunks or the number of threads can be easily changed to optimize the performance.

In conclusion, multithreading is a powerful technique for improving the performance of computationally intensive tasks, such as finding prime numbers. Java provides a rich set of tools for implementing multithreaded solutions, making it a great choice for these types of problems.