Finding prime numbers in user specified array

Question

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<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.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<>(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);

    }
}

Answer 1

Indentation

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

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

---

Naming

Don't name loop variables any random number:

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

You should give them a name describing what they are:

for (int potential_prime = start; potential <= end; potential++) {
    for (int divisor = 2; divisor < 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.

Answer 2

Multi-threading, part one

(disclaimer: largely copied from my answer here.)

The preferred way of doing multi-threading since Java 5 is to use an ExecutorService to help you manage the lifecycle of threads. You should read up more on Oracle's tutorial to understand how they are used.

In addition, since you want each thread to compute and return a result for you, you should be looking at the Callable<V> interface for your Prime class. Implementations override the call() method to return an appropriate result of type V.

Multi-threading, part two

Going back to my other answer mentioned above, you can look at how to use an ExecutorService to create Futures to obtain your results asynchronously, or to chain CompletableFutures if you are on Java 8.

Miscellaneous

1. In your current approach, Thread already implements Runnable, so that declaration for Prime class is redundant.

2. Scanner scan = new Scanner(System.in); is redundant in the Prime class too.

Answer 3

You could do some other speedup, you only need check every second number, so your outer loop would become

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

and as already said, you don't need to check every value up to the maximum number you have