算术数计算问题中的该循环是否可并行化？

你提到想对这段代码的外部循环做并行化，认为divisor_count和divisor_sum可以作为线程的归约变量，但困惑内层循环修改n是否会导致外部循环迭代彼此依赖、无法并行化——结论很明确：这段代码的外部循环完全无法直接并行化，核心原因就是共享变量n在内层循环中被修改，导致外层循环的迭代之间存在强依赖关系：

代码片段 #

unsigned int divisor_count = 1;
unsigned int divisor_sum = 1;
unsigned int power;
for (unsigned int p = 3; p * p <= n; p += 2)
{
    unsigned int count = 1, sum = 1;
    for (power = p; n % p == 0; power *= p, n /= p)
    {
        ++count;
        sum += power;
    }
    divisor_count *= count;
    divisor_sum *= sum;
}

关键依赖分析 #

1. 循环条件的依赖：外层循环的终止条件p * p <= n中的n会被内层循环不断修改（每次整除时执行n /= p），后续外层循环的迭代是否执行，完全依赖于前面迭代对n的修改结果。
2. 计算逻辑的依赖：内层循环判断n % p == 0时，n已经是前面所有外层迭代处理后剩余的数值——前面的迭代已经移除了n中包含的更小素因子，后续的p只会尝试分解剩余部分。如果并行执行外层循环，每个线程拿到的初始n都是原始值，会重复处理已经被其他线程移除的因子，同时多个线程并发修改n会引发数据竞争，最终的divisor_count和divisor_sum结果完全错误。

关于归约变量的补充 #

虽然divisor_count和divisor_sum的更新是乘法操作，理论上符合归约的形式，但归约的前提是各个并行迭代的计算是完全独立的，而这里每个迭代的计算逻辑和输入（n的当前值）都依赖于前面的迭代，所以根本不满足并行归约的条件。

内容的提问来源于stack exchange，提问作者Pavle Šarenac