Parallel SieveOfEratosthenes（埃拉托色尼平行筛）

问：

我正在尝试对埃拉托色尼的筛子进行 parelleize，这样做的想法是这样的：首先找到素数到 N 的平方根，这些素数将均匀分布到线程数。这些 thrare 现在对于每个素数，它们都有交叉倍数，并在 byteArray 中标记该数字是否为素数。 最后，我将按顺序遍历这个字节数组并收集所有素数值。

我面临的问题是，找到的素数数量不正确，并且一定在我看不到的地方存在同步问题，因为 numOfPrimes 每次都在变化

我将尽可能多地粘贴代码。

public class Para_SieveOfEratosthenes {

static int number_to_find_primes = 2000000;
static int square_of_num = (int) Math.sqrt(number_to_find_primes);
static int square_of_square = (int) Math.sqrt(square_of_num);


static int cells = (number_to_find_primes / 16) + 1;
static public byte[] byteArray2 = new byte[cells];
static int num_of_threads = 3;
static int numOfPrimes = 2;

总的来说，我首先使用另一个类中的另一种方法来查找素数。我想这可能是问题所在，因为也许在此方法中完成的字节数组中的交叉不会转到 byteArray2？

public static void main(String[] args) {
    SieveOfEratosthenes seqSiev = new SieveOfEratosthenes(square_of_square);
    int[] primes = seqSiev.getPrimes();
    //Get the num of primes found in the seq algo
    numOfPrimes += primes.length;

这部分代码看起来都很好，因为它平均划分了素数并创建了应有的线程

 Thread[] threads = new Thread[num_of_threads];
    int primes_per_thread = primes.length / num_of_threads;
    int extra_primes = primes.length % num_of_threads;
    int start_index = 0;
    int end_index = 0;

  
    int value_length = number_to_find_primes / num_of_threads;
  

    for (int i = 0; i < num_of_threads; i++, extra_primes--) {
        start_index = end_index;
        end_index = start_index + primes_per_thread + (extra_primes > 0 ? 1 : 0);
        int[] thread_primes = Arrays.copyOfRange(primes, start_index, end_index);
        
       
        threads[i] = new Thread(new SieveWorker(i,thread_primes));

     }

我现在启动线程并等待连接，然后收集素数

 for (int i = 0; i < num_of_threads; i++) {
        threads[i].start();
    }

    for (int i = 0; i < num_of_threads; i++) {
        try { threads[i].join(); } catch (InterruptedException e) {}
    }

    int[] arr=collectPrimes();
    System.out.println(arr.length);

这是 collectPrime 方法，它取自 SieveOfEratosthenes，因为它是预码，因此被认为是正确的

 private static int[] collectPrimes() {
    

    int start = (square_of_num % 2 == 0) ? square_of_num + 1 : square_of_num + 2;
    
    for (int i = start; i <= number_to_find_primes; i += 2){
       
      if (isPrime(i))
        numOfPrimes++;
    }
    System.out.println(numOfPrimes);
    int[] primes = new int[numOfPrimes];

    primes[0] = 2;

    int j = 1;

    for (int i = 3; i <= number_to_find_primes; i += 2)
      if (isPrime(i))
       {
        primes[j++] = i;
       }

    return primes;
  }

这是线程类：

static class SieveWorker implements Runnable{

    public int id;
    public int[] work;
    public int num_primes;
    public int value_start;
    public int value_end = number_to_find_primes;
    

    public SieveWorker(int id,int[] work  ){
        this.id = id;
        this.work = work;
       }
   @Override
    public void run() {
        for (int i = 0; i < work.length; i++) {
            this.value_start = work[i];
            sieve(work[i]);
        }}

这些是做筛子的方法

static  void sieve(int prime) {
    //System.out.println("We are traversing: "+prime);
    
    while (prime != -1) {
        traverse(prime);
        prime = nextPrime(prime);
        numOfPrimes++;
      }}

private static void traverse(int prime) {
    for (int i = prime*prime; i <= number_to_find_primes; i += prime * 2)
      mark(i);
  }

private static void mark(int num) {
    int bitIndex = (num % 16) / 2;
    int byteIndex = num / 16;
    byteArray2[byteIndex] |= (1 << bitIndex);
  }

 private static int nextPrime(int prev) {
    for (int i = prev + 2; i <= square_of_num; i += 2)
      if (isPrime(i))
        return i;

    return -1;
  }

如果有人知道错误在哪里，我将不胜感激，不确定如何在不失去代码价值的情况下缩小这篇文章。谢谢