Currently I'm trying to implement a prime finder using threads in java. Unfortunately it does not seem to work the way I intend it to.

What I basically want is that I have a while(true) loop to generate numbers indefinitely. After a number is generated,a thread should grab that number and check if it is a prime number. While the first thread is still checking for prime, the second thread already grabbed the next number to check for prime and so on.

Right now the number generating does work but all threads seem to use the same number, which makes no sense for my implementation.

This is the current state of my project:

public class Main {
    public static void main(String[] args) {
        int logicalCores = Runtime.getRuntime().availableProcessors();
        int startFrom = 0;
        startCalc(logicalCores, startFrom);
    }

    public static void startCalc(int threadCount, int startFrom){
        for (int i = 0; i < threadCount; i   ){
            PrimeCalculator calculator = new PrimeCalculator(startFrom, i);
            Thread thread = new Thread(calculator);
            thread.start();
        }    
    }
}

import static java.lang.Thread.sleep;

public class PrimeCalculator implements Runnable{    
    int startingCounter;
    int id;
    public PrimeCalculator(int counter, int id){
    this.startingCounter = counter;
    this.id = id;
    }

    @Override
    public void run() {
        Integer counter = startingCounter;

        while(true){                
            if (isPrime((counter))){
                System.out.printf("Thread with ID %d found that %d is a prime! \n", id, counter );

                try{
                    sleep(10000);
                } catch (Exception e){    
                }    
            }

            synchronized (counter){
                counter  ;
            }
        }
    }

    public static boolean isPrime(int n)
    {
        if (n == 2 || n == 3 || n == 5) return true;
        if (n <= 1 || (n&1) == 0) return false;
        for (int i = 3; i*i <= n; i  = 2)
            if (n % i == 0) return false;
        return true;
    }    
}

The problem is that all threads seem to keep checking the same number. E.g the number is 2, but all 16 Threads of my CPU check for prime while in reality a thread like Thread0 should check the number 2 for prime while others are already checking an increment of the counter (e.g Thread15 is already at 16) etc.

EDIT:

I think I need to give a better example of the expected behaviour.

Let's say I have a computer with 4 cores and 4 threads. This would make the logicalCores variable in my main method 4 and create 4 threads in the function "startCalc".

Now a loop should generate numbers from a defined starting point. Let's just say that point is 0. What should happen now is that a thread, let's just call it thread0 is taking that number and checks if it is a prime. In the meantime the loop generated an increment of the counter and sits at "1" now. Now, because thread0 is still checking if 0 is a prime, a second thread, thread1, grabbed the current counter with the value "1" and is checking if "1" is a prime.

The goal here is that each thread is checking a number for prime in a way which prevents double checking. e.g (we DO NOT want thread0 to check if 1 is a prime because thread1 already did)

CodePudding user response：

Your counter should be a value shared by all threads, so that incrementing it from one thread affects all concurrent threads.

Simplest way to do that is to use a static field. Then use some kind of synchronization to avoid threads incrementing / reading counter concurrently.

public class Main {
  public static void main(String[] args) {
    int logicalCores = Runtime.getRuntime().availableProcessors();
    int startFrom = 0;
    startCalc(logicalCores, startFrom);
  }

  public static void startCalc(int threadCount, int startFrom) {
    PrimeCalculator.startAt(startFrom); //Set this for all threads
    for (int i = 0; i < threadCount; i  ) {
      PrimeCalculator calculator = new PrimeCalculator(i);
      Thread thread = new Thread(calculator);
      thread.start();
    }
  }
}

import static java.lang.Thread.sleep;

public class PrimeCalculator implements Runnable {

  static int counter; //Use static variable
  int id;

  public static void startAt(int counterStart) { //Set start once for all threads
    counter = counterStart;
  }

  public PrimeCalculator(int id) {
    this.id = id;
  }

  @Override
  public void run() {
    while (true) {
      int current = incrementAndGetCounter();

      if (isPrime((current))) {
        System.out.printf("Thread with ID %d found that %d is a prime! \n", id, current);

        try {
          sleep(1000);
        } catch (Exception e) {
        }
      }
    }
  }

  public static boolean isPrime(int n) {
    if (n == 2 || n == 3 || n == 5)
      return true;
    if (n <= 1 || (n & 1) == 0)
      return false;
    for (int i = 3; i * i <= n; i  = 2)
      if (n % i == 0)
        return false;
    return true;
  }

  //Use synchronized method to increment and get value
  //to prevent one thread incrementing it while another one is reading it
  private static synchronized int incrementAndGetCounter() {
    return counter  ;
  }
}