Find prime numbers in an array using multithreading

Question

I'm currently trying to modify a sequential prime program I worked on and incorporate multithreading. I'd like to specify the amount of threads to split the work, and then have each thread run an algorithm to find primes, then display how many primes are in each thread.

The problem seems to be that each thread is running the algorithm on the entire array, it's not splitting the array in the desired threads I specify. I experimented with some other things, but they pretty much just caused more errors.

As of right now, I'm experimenting on an array of 1000 numbers. Once I get it working, I would put millions of numbers in the array, but I just wanted to do less numbers first. There should be 168 prime numbers in the array of 1000. The problem is each thread is returning 168 primes, which is leading me to believe each thread is doing the same thing, not splitting up the work. My question is, how can I take this program, and get it to split the array and run the algorithm that way? So 0 to 499 would run the algorithm and display the amount of primes withing thread 0, then 500 to 1000 would run the alg and display how many primes are within that thread.

Here's my code - Prime.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Prime extends Thread {


    Scanner scan = new Scanner(System.in);

    static long [] primes = new long [1000];
    static ArrayList<Integer> primeList = new ArrayList<Integer>();


      //int max = num;
   public int count = 0;


   public void run() {
        for (int n = 2; n<=primes.length; n++) {
              boolean prime = true;
                  for (int j = 2; j < n; j++) {
                          if (n%j == 0){
                              prime = false;
                              break;
                                }
                  }

                if (prime){
                        count++;
                        primeList.add(n);

                }

          }
   }
}

Worker.java

 import java.util.ArrayList;
    import java.util.Scanner;

    public class Worker {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);

        System.out.println("How Many threads? ");
        int nThreads = scan.nextInt();  // Create variable 'n'  to handle whatever integer the user specifies.  nextInt() is used for the scanner to expect and Int.

        final Prime[] pThreads = new Prime[nThreads];

        long startTime = System.currentTimeMillis();
        for(int i = 0; i<nThreads; i++){
            pThreads[i] = new Prime();
            pThreads[i].start();

        }
        try {
            for (int i = 0; i < nThreads; i++)
                pThreads[i].join();
        } catch (InterruptedException e) {
            }
            long stopTime = System.currentTimeMillis();

            long elapsedTime = stopTime - startTime;
            System.out.println("Execution time = : "+  elapsedTime);

            System.out.println("----------------------------------------------------");

            int cores = Runtime.getRuntime().availableProcessors();
            System.out.println("How many Cores this Java Program used: " + cores);



          for (int i = 0; i < nThreads; i++)
              System.out.println("Thread " + i + "  Prime count: " + pThreads[i].count); // Display Thread count
         System.out.println("Total prime count: " + Prime.primeList.size()); // Output total amount of primes from the Array List
         for (int i = 0; i < 100; i++) // Display first 100 primes.
            System.out.println(Prime.primeList);

         }

    }

Any help would be appreciated. Thanks.

Answer 1

The problem is that each thread is looping through all values for (int n = 2; n<=primes.length; n++). Note that the values in primes are not used, just the length. You may want to try to give Prime a constructor that takes the range of numbers that you want to process:

public class Prime extends Thread {

    static ArrayBlockingQueue<Integer> primeList;
    int start, end;

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

    ...

        for (int n = start; n <= end n++) {

In the setup, pass a segment to each thread. Also, don't forget to set Primes.primeList. Note that ArrayList is not thead safe in Java, so that having all the threads appending to the same list is a really terrible idea. Use something like java.util.concurrent.ArrayBlockingQueue instead (notice above). E.g., in Worker:

Prime.primeList = new ArrayBlockingQueue<>(1000); // Guaranteed to be enough
int step = 1000 / nThreads + 1;
for(int i = 0; i<nThreads; i++){
    pThreads[i] = new Prime(i * step, Math.min(1000, (i + 1) * step - 1));
    pThreads[i].start();
}

All this will help you patch up your exising code and maybe even get it working. I would highly recommend reading a real tutorial on Java threads as well as finding primes so you understand what you are doing better. A quick SO code fix will not address the fundametal issues in your code.

Answer 2

As far as I understood, you have an array of integers [a1, a2, ..., an] and you would like to find which of these integers are primes.

You want to do this by giving each thread some subsets of these integers for a verification.

---

If this is the case, than you are doing it in a wrong way. You would be way faster by just finding the maximum of your elements in an array. Then run Sieve of Eratosthenes to get all primes in below your biggest number (note that you do not need to divide through all integers, just up to sqrt(n), because the biggest prime can be sqrt(n))

Then run through your array another time time and check whether you answer is in the your map of primes.

P.S. the similar idea holds if you want to factorize many numbers.

---

If you want to learn how to do threads in Java, than this is not the answer you are looking for.

Answer 3

I took another approach without thread blocking. The reason this is possible is that BigInteger.isProbablePrime() is valid for all 32 bit integers. Here is the code:

Prime.java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Prime extends Thread {
    public int count = 0;
    public int lowerBound;
    public List<Integer> primeList = new ArrayList<>();

    public void run() {
        for (int n = lowerBound; n <= lowerBound+1000; n++) {
            BigInteger bi = BigInteger.valueOf(n);
            if (bi.isProbablePrime(100)){
                count++;
                primeList.add(n);
            }
        }
    }
}

And Worker.java:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Worker {
    public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         System.out.println("How Many threads? ");
         int nThreads = scan.nextInt();  // Create variable 'n'  to handle whatever integer the user specifies.  nextInt() is used for the scanner to expect and Int.

         final Prime[] pThreads = new Prime[nThreads];
         long startTime = System.currentTimeMillis();
         for(int i = 0; i<nThreads; i++){
             pThreads[i] = new Prime();
             pThreads[i].lowerBound = 2+1000*i;
             pThreads[i].start();
         }

         try {
             for (int i = 0; i < nThreads; i++)
                 pThreads[i].join();
         } catch (InterruptedException e) {
         }
         long stopTime = System.currentTimeMillis();
         long elapsedTime = stopTime - startTime;
         System.out.println("Execution time = : "+  elapsedTime);
         System.out.println("----------------------------------------------------");
         int cores = Runtime.getRuntime().availableProcessors();
         System.out.println("How many Cores this Java Program used: " + cores);
         for (int i = 0; i < nThreads; i++)
             System.out.println("Thread " + i + "  Prime count: " + pThreads[i].count); // Display Thread count
         List<Integer> allPrimes = new ArrayList<>();
         for (Prime p : pThreads) {
             allPrimes.addAll(p.primeList);
         }
         System.out.println("Total prime count: " + allPrimes.size()); // Output total amount of primes from the Array List
         for (int i = 0; i < 100; i++) // Display first 100 primes.
             System.out.println(allPrimes.get(i));
     }
 }

Result:

How Many threads?
2
Execution time = : 35
How many Cores this Java Program used: 12
Thread 0  Prime count: 168
Thread 1  Prime count: 135
Total prime count: 303
...