循环上限设为200万时无控制台输出且无报错，求原因

尝试通过迭代计算200万以下所有质数的和，使用的C++代码如下，当循环上限设为200万时控制台无输出且无报错，但设为10万左右时可正常运行，请问这是内存问题还是其他原因？

int main() {
    int naturalNumber = 2;
    int divider = 0;
    int rest = 1;
    long long int sumOfPrimes = 0;
    while (naturalNumber <= 2000000) {
        divider = naturalNumber;
        while (rest != 0) {
            divider--;
            rest = naturalNumber % divider;
        }
        rest = 1;
        if (divider == 1) {
            sumOfPrimes = sumOfPrimes + naturalNumber;
        }
        naturalNumber++;
    }
    std::cout << sumOfPrimes;
}

这不是内存问题，核心原因是你的质数判断算法效率极低，导致程序运行时间过长，看起来像是无响应、无输出，而非程序出错。

原算法的低效点 #

判断一个数naturalNumber是否为质数时，你从divider = naturalNumber开始递减，直到余数为0才停止。对于质数来说，这个循环要一直执行到divider=1——比如判断200万这个数是否为质数，需要循环1999999次。
整体时间复杂度为O(n²)，当n达到200万时，总运算量会达到天文数字，程序需要运行数分钟甚至更久才能完成，远超过你能等待的时间，因此看起来像是“无输出”。

优化方案 #

1. 优化单质数判断逻辑

判断一个数是否为质数，只需检查到它的平方根即可——如果一个数n有大于sqrt(n)的因数，那必然存在一个对应的小于sqrt(n)的因数。修改后的判断逻辑：

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

单个质数判断的时间复杂度降到O(√n)，整体效率会大幅提升。

2. 使用埃拉托斯特尼筛法（埃氏筛）

这是计算大范围质数和的最优方法之一，时间复杂度为O(n log log n)，能快速筛选出200万以内的所有质数：

#include <iostream>
#include <vector>

int main() {
    const int limit = 2000000;
    std::vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= limit; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    long long sumOfPrimes = 0;
    for (int i = 2; i <= limit; ++i) {
        if (isPrime[i]) {
            sumOfPrimes += i;
        }
    }
    
    std::cout << sumOfPrimes << std::endl;
    return 0;
}

这个版本的程序能在极短时间内完成计算并输出结果。

内容的提问来源于stack exchange，提问作者Mr.Prince