I have a program that searches for prime numbers in an array specified by the user.  The program starts by asking how big the user wants the array to be, then asks how many threads to split the computations.I tested 1000 numbers, 10,0000, 100,000 and 1 million, and they all yielded results in a fairly reasonably time.  1 million numbers took about 2 minutes.  When I tried 10 million numbers, well.. the program is still running well over 2 hours with no results.I'm wondering if the speed is normal, or if there's something fundamentally wrong with my find prime algorithm that is making it take so long to yield the desired results.Prime.Javaimport java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.util.concurrent.ArrayBlockingQueue;public class Prime extends Thread implements Runnable {    //public List<Integer> primeList = new ArrayList<>();    static ArrayBlockingQueue<Integer> primeList;    int start, end;    //int max = num;    public int count = 0;    public Prime(int start, int end) {        this.start = start;        this.end = end;    }    Scanner scan = new Scanner(System.in);   public void run() {       for (int n = start; n <= end; n++) {           boolean prime = true;                  for (int j = 2; j < n; j++) {                          if (n%j == 0){                              prime = false;                              break;                                }                  }                  if(prime && n !=1 && n!=0){   // Added conditions so it does not count 1 or 0 as prime.                                       count++;                        primeList.add(n);                }          }   }}Worker.Javaimport java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.util.concurrent.ArrayBlockingQueue;public class Worker {    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        System.out.println(How big would you like the array? );        int num = scan.nextInt();        int [] primes = new int [num];        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();        Prime.primeList = new ArrayBlockingQueue<>(primes.length); // Guaranteed to be enough        int step = primes.length / nThreads + 1;        for(int i = 0; i<nThreads; i++){            pThreads[i] = new Prime(i * step, Math.min(primes.length, (i + 1) * step - 1));            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);            System.out.println(Array length  + primes.length);          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            // System.out.println(Prime.primeList);    }}
Finding prime numbers in user specified array
java;algorithm;array;multithreading;primes