java - 使用多线程在数组中查找质数

Question

我目前正在尝试修改我工作的顺序素数程序并合并多线程。我想指定线程的数量来拆分工作，然后让每个线程运行一个算法来查找素数，然后显示每个线程中有多少个素数。

问题似乎是每个线程都在整个数组上运行算法，它没有在我指定的所需线程中拆分数组。我尝试了一些其他的东西，但它们几乎只会导致更多的错误。

截至目前，我正在对 1000 个数字的数组进行试验。一旦我开始工作，我会在数组中放入数百万个数字，但我只想先做更少的数字。 1000 的数组中应该有 168 个质数。问题是每个线程都返回 168 个质数，这让我相信每个线程都在做同样的事情，而不是拆分工作。我的问题是，我怎样才能使用这个程序，让它拆分数组并以这种方式运行算法？因此 0 到 499 将运行算法并显示线程 0 中素数的数量，然后 500 到 1000 将运行算法并显示该线程中有多少素数。

这是我的代码 - 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);

         }

    }

如有任何帮助，我们将不胜感激。谢谢。

Answer 1

问题是每个线程都在遍历所有值 for (int n = 2; n<=primes.length; n++) .请注意 primes 中的值没有使用，只是长度。您可能想尝试提供 Prime采用您要处理的数字范围的构造函数:

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++) {

在设置中，将一个段传递给每个线程。另外，不要忘记设置 Primes.primeList .注意 ArrayList在 Java 中不是线程安全的，因此将所有线程附加到同一个列表是一个非常糟糕的想法。使用类似 java.util.concurrent.ArrayBlockingQueue 的东西相反(上面的通知)。例如，在 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();
}

所有这些都将帮助您修补现有代码，甚至可能使其正常工作。我强烈建议阅读有关 Java 线程的真实教程以及查找素数，以便您更好地了解自己在做什么。快速的 SO 代码修复不会解决代码中的基本问题。