Finding prime numbers in user specified array 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.Java

import 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&lt;Integer&gt; primeList = new ArrayList&lt;&gt;();

    static ArrayBlockingQueue&lt;Integer&gt; 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 &lt;= end; n++) {
           boolean prime = true;
                  for (int j = 2; j &lt; n; j++) {
                          if (n%j == 0){
                              prime = false;
                              break;
                                }
                  }

                  if(prime &amp;&amp; n !=1 &amp;&amp; n!=0){   // Added conditions so it does not count 1 or 0 as prime.               
                        count++;
                        primeList.add(n);

                }

          }
   }
}


Worker.Java

import 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&lt;&gt;(primes.length); // Guaranteed to be enough
        int step = primes.length / nThreads + 1;
        for(int i = 0; i&lt;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 &lt; 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 &lt; 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);

    }
}
Indentation

Your indentation in run() and other methods can be improved:


boolean prime = true;
       for (int j = 2; j &lt; n; j++) {
               if (n%j == 0){
                   prime = false;
                   break;
                     }
       }



At first, I thought that was another level of nesting.  You should write it like this.

boolean prime = true;
for (int j = 2; j &lt; n; j++) {
    if (n%j == 0){
        prime = false;
        break;
    }
}




Naming

Don't name loop variables any random number:


for (int n = start; n &lt;= end; n++) {
    for (int j = 2; j &lt; n; j++) {



You should give them a name describing what they are:

for (int potential_prime = start; potential &lt;= end; potential++) {
    for (int divisor = 2; divisor &lt; n; divisor++) {




Algorithm

When you check whether any number n is prime, you check the divisors j from 2 to n.  If a divisor j is greater than the floor (sqrt (n)), you need not check it.  This is because once you get above this number and less than n / 2, you are only checking for the reverse pairs you checked before (4 * 5 == 5 * 4), and any number greater than n / 2 cannot go into n more than once.  Eliminating these extra checks could greatly speed your algorithm up on very large numbers.