并行埃拉托斯特尼筛法多线程实现问题：质数计数异常求助

问题现象 #

当设置num_threads = 1时，程序能正确统计质数数量；但增加线程数后，质数计数结果明显偏少，结果异常。

核心错误原因 #

1. 数组参数值传递导致副本问题 #

multithread_calc函数的isPrime参数是值传递，每个线程都会创建原数组的副本，线程内对数组的修改只作用于副本，原数组完全没被修改。最终统计的是未正确筛选的初始数组，结果必然错误。

2. 共享变量的竞态条件 #

多个线程同时修改同一个found引用变量，没有任何同步机制，会导致计数丢失（比如两个线程同时执行found_chunk += isPrime[i]，最终只累加了一次）。

3. 任务拆分逻辑错误 #

• 错误地将sqrt(lastNumber)范围内的质数筛选拆分到多个线程并行处理，这部分是埃氏筛的基础，必须先全局完成所有小质数的筛选，否则会出现漏标记或重复标记的问题。
• 内存块（memorySize）与数值块（lastNumber）的拆分逻辑不匹配，索引映射混乱，导致区间统计错误。

修复方案 #

1. 修正数组传递方式 #

将multithread_calc的isPrime参数改为引用传递，确保所有线程操作同一个数组：

void multithread_calc(vector<int>& isPrime, ...)

创建线程时传递数组的引用：

auto th = thread(&multithread_calc, ref(isPrime_), ...);

2. 解决竞态条件 #

取消共享的found变量，改为每个线程返回自己负责区间的质数计数，主线程最后汇总所有结果：

• 修改multithread_calc返回值为int，移除found_chunk引用参数
• 用future<int>接收每个线程的返回值，主线程等待所有线程完成后累加结果

3. 重构任务拆分逻辑 #

正确的并行埃氏筛流程：

1. 主线程预处理：先筛选出sqrt(lastNumber)以内的所有质数，这部分串行执行，为后续标记提供基础质数列表。
2. 多线程并行标记：将大于sqrt(lastNumber)的区间拆分为多个子区间，每个线程用预处理得到的质数列表，标记自己区间内的合数。
3. 多线程统计：每个线程统计自己区间内的质数数量，主线程汇总所有线程的结果，加上预处理阶段的质数数量和偶质数2的计数。

修复后的完整代码 #

const long int lastNumber = 1LL * 1000 * 1000 * 1000;

#include <iostream>
#include <vector>
#include <cmath>
#include <thread>
#include <future>
#include <cassert>
#include <sys/time.h>

using namespace std;

double seconds()
{
    timeval now;
    gettimeofday(&now, NULL);
    return now.tv_sec + now.tv_usec / 1000000.0;
}

// 线程任务：标记指定区间内的合数，并统计质数数量
int thread_sieve(vector<int>& isPrime, const vector<int>& base_primes, long long start, long long end)
{
    // 标记当前区间内的合数
    for (int p : base_primes) {
        // 找到区间内第一个大于等于p*p的数，或者第一个能被p整除的数
        long long first = max((long long)p * p, ((start + p - 1) / p) * p);
        // 如果是偶数，调整为奇数（因为我们只存储奇数的标记）
        if (first % 2 == 0) first += p;
        // 标记所有p的奇数倍数
        for (long long j = first; j <= end; j += 2 * p) {
            isPrime[(j - 1) / 2] = 0;
        }
    }

    // 统计当前区间内的质数数量
    int count = 0;
    long long start_idx = (start - 1) / 2;
    long long end_idx = (end - 1) / 2;
    for (long long i = start_idx; i <= end_idx; ++i) {
        if (isPrime[i]) {
            count++;
        }
    }
    return count;
}

int eratosthenes(long long lastNumber)
{
    if (lastNumber < 2) return 0;

    int found = 1; // 先计数偶质数2
    const long long lastNumberSqrt = (long long)sqrt((double)lastNumber);
    int memorySize = (lastNumber - 1) / 2;
    vector<int> isPrime(memorySize, 1); // 索引i对应数值2*i+1

    // 第一步：主线程筛选sqrt(lastNumber)以内的质数
    for (long long i = 3; i <= lastNumberSqrt; i += 2) {
        if (isPrime[(i - 1) / 2]) {
            for (long long j = i * i; j <= lastNumberSqrt; j += 2 * i) {
                isPrime[(j - 1) / 2] = 0;
            }
        }
    }

    // 收集基础质数列表（用于后续线程标记）
    vector<int> base_primes;
    for (long long i = 3; i <= lastNumberSqrt; i += 2) {
        if (isPrime[(i - 1) / 2]) {
            base_primes.push_back(i);
            found++; // 统计sqrt范围内的质数
        }
    }

    // 第二步：多线程处理大于sqrt(lastNumber)的区间
    int num_threads = thread::hardware_concurrency(); // 使用硬件线程数
    if (num_threads == 0) num_threads = 2;

    vector<future<int>> futures;
    long long chunk_size = (lastNumber - lastNumberSqrt) / num_threads;

    for (int i = 0; i < num_threads; ++i) {
        long long start = lastNumberSqrt + 1 + i * chunk_size;
        long long end = (i == num_threads - 1) ? lastNumber : lastNumberSqrt + (i + 1) * chunk_size;
        // 确保start是奇数
        if (start % 2 == 0) start++;
        // 如果start超过end，跳过
        if (start > end) continue;

        futures.emplace_back(async(launch::async, thread_sieve, ref(isPrime), ref(base_primes), start, end));
    }

    // 汇总所有线程的计数
    for (auto& fut : futures) {
        found += fut.get();
    }

    return found;
}

int main(int argc, char* argv[])
{
    int found = 0;
    printf("Primes between 2 and %lld\n\n", lastNumber);
    printf("Parallel Sieve\n");
    double startTime = seconds();
    found = eratosthenes(lastNumber);
    double duration = seconds() - startTime;
    printf("%d primes found in %.3fs\n\n", found, duration);

    return 0;
}

修复说明 #

• 改用引用传递数组，确保所有线程操作同一数据
• 用future接收线程返回值，避免共享变量的竞态问题
• 先串行完成基础质数筛选，再并行处理大区间的标记和统计，符合埃氏筛的逻辑
• 自动适配硬件线程数，提升并行效率

内容的提问来源于stack exchange，提问作者DeadlyKitten999