如何用OpenMP正确并行化带条件循环？质数计数结果异常排查

我一眼就猜到问题出在哪了——你肯定是多个线程同时在修改同一个统计质数的计数器变量对吧？这种情况在OpenMP并行里太常见了！

问题根源：非原子操作的竞争 #

比如你可能写了类似这样的代码：

int count = 0;
#pragma omp parallel for
for (int i = 2; i < n; i++) {
    if (is_prime(i)) {
        count++; // 这里就是坑！
    }
}

count++看起来是一行代码，但实际上它是三个独立的操作：读取当前count值 → 加1 → 写回新值。当多个线程同时执行这三步时，就会出现“抢着改”的情况：比如线程A刚读完count=5，还没来得及加1写回去，线程B也读到了count=5，然后两个线程都把count改成6，相当于白白丢了一次计数！这就是为什么每次结果都不一样。

两种简单有效的解决办法 #

1. 用OpenMP的归约（Reduction）子句（推荐）

归约会让每个线程先维护自己的私有计数器副本，并行计算结束后再把所有线程的结果合并起来，从根源上避免竞争。只需要修改并行指令：

int count = 0;
#pragma omp parallel for reduction(+:count) // 这里加个reduction(+:count)
for (int i = 2; i < n; i++) {
    if (is_prime(i)) {
        count++;
    }
}

这种方式效率比同步锁高很多，因为不需要线程之间频繁等待。

2. 用原子操作保护计数器

如果不想用归约，也可以给count++加个原子操作的保护，确保这个递增过程是“不可打断”的：

int count = 0;
#pragma omp parallel for
for (int i = 2; i < n; i++) {
    if (is_prime(i)) {
        #pragma omp atomic // 加这个指令保护count++
        count++;
    }
}

原子操作会强制让这个递增操作作为一个整体执行，不会被其他线程打断，也就不会丢计数了。

额外提醒：如果是筛法的话还要注意数组竞争 #

要是你用的是埃拉托斯特尼筛法，多个线程同时修改同一个筛数组（比如标记非质数），那也会出现竞争问题，这时候可能需要用#pragma omp critical临界区或者更精细的分区策略，但如果是普通的试除法，上面两种方法就足够解决你的问题啦！

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