C++求指定范围内质数：sqrt优化后判断逻辑疑问

嘿，作为C++新手能想到用sqrt()来优化循环效率，这思路已经很到位啦！我来帮你把质数判断的逻辑理清楚，把你的代码补全并解释清楚关键部分～

质数判断的核心逻辑 #

质数的定义是：大于1的自然数，除了1和它本身之外没有其他正因数。所以判断逻辑可以拆解为：

• 首先排除小于2的数，它们肯定不是质数；
• 对于大于等于2的数，从2开始遍历到它的平方根（用sqrt(i)），如果遍历过程中发现有任何数能整除它，那它就不是质数；
• 要是遍历完所有小于等于sqrt(i)的数都没能整除它，那它就是质数。

补全后的完整代码 #

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    vector<int> prime_numbers;  // 用int比double更合适，质数都是整数
    int upper_limit;

    cout << "请输入一个正整数：";
    cin >> upper_limit;

    // 遍历2到upper_limit的所有数（1不是质数，直接跳过）
    for (int i = 2; i <= upper_limit; ++i) {
        bool is_prime = true;  // 先假设当前数是质数

        // 遍历从2到sqrt(i)的所有数，检查是否有因数
        for (int j = 2; j <= sqrt(i); ++j) {
            if (i % j == 0) {  // 如果能被整除，说明不是质数
                is_prime = false;
                break;  // 找到因数就不用继续循环了，节省时间
            }
        }

        if (is_prime) {  // 如果最终还是true，说明是质数，加入vector
            prime_numbers.push_back(i);
        }
    }

    // 输出结果
    cout << "1到" << upper_limit << "之间的质数是：" << endl;
    for (int prime : prime_numbers) {
        cout << prime << " ";
    }
    cout << endl;

    return 0;
}

关键细节解释 #

• 为什么用sqrt(i)？：如果一个数i有一个大于sqrt(i)的因数，那对应的另一个因数肯定小于sqrt(i)，所以只需要检查到平方根就够了，能大幅减少循环次数。
• bool is_prime = true的作用：先默认当前数是质数，一旦找到能整除的数就把它设为false，最后根据这个布尔值判断是否加入质数列表。
• break语句：找到第一个因数后就立刻跳出内层循环，不用做多余的检查，提升效率。
• 为什么从i=2开始？：1不是质数，所以直接从2开始遍历，少做一次无用检查。

如果还有其他疑问，比如想尝试更高效的筛法优化，随时问哦～

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