输入65535时素数计算耗时骤增的原因咨询

哈哈，这个问题的核心完全出在你的isPrime函数上——里面有两个致命的逻辑错误，直接导致了测试时的耗时异常！让我给你拆解清楚：

1. 素数判断逻辑完全颠倒 #

你写的isPrime函数里，当num % divisor == 0时（也就是num能被divisor整除，说明num是合数），代码返回true（误以为是素数）；而只有当所有除数都无法整除num时，才应该返回true（确实是素数）。这完全搞反了判断逻辑！

2. 循环条件完全不合理 #

当前循环条件是divisor != INT_MAX，这意味着函数会一直循环到divisor达到整数最大值，完全没有必要。正确的终止条件应该是divisor * divisor <= num（或者divisor <= sqrt(num)）——因为如果num有大于其平方根的因数，那么必然存在一个对应的小于平方根的因数，所以检查到平方根就足够了，能大幅减少循环次数。

针对你的测试案例逐一解释 #

输入65533时耗时短 #

findNextPrime会把初始的65533（奇数）加2变成65535，然后调用isPrime(65535)。divisor从3开始，65535能被3整除（65535=3×21845），所以isPrime立刻返回true，流程直接结束，耗时自然极短。

输入65535时耗时暴增 #

findNextPrime把初始的65535（奇数）加2变成65537，调用isPrime(65537)。而65537是一个素数（费马素数），由于你的isPrime函数循环条件错误，它会从3开始，每次加2，一直检查到divisor等于65537时（此时65537 % 65537 == 0，返回true）才终止循环。这中间要执行约3万多次循环，耗时自然大幅增加。

输入65539时耗时短 #

findNextPrime把初始的65539（奇数）加2变成65541，调用isPrime(65541)。65541能被3整除（65541=3×21847），所以isPrime立刻返回true，流程快速结束，耗时很短。

修正后的代码 #

我已经修复了这两个错误，同时优化了findNextPrime的逻辑（只检查奇数，减少不必要的判断）：

#include "stdafx.h"
#include <string>
#include <iostream>
#include <chrono>
#include <cmath> // 用于sqrt函数

bool isPrime(int num) {
    // 处理特殊情况：小于等于1不是素数，2是唯一的偶素数
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false; // 偶数直接排除

    int sqrtNum = static_cast<int>(sqrt(num));
    // 只检查奇数除数，从3到num的平方根
    for (int divisor = 3; divisor <= sqrtNum; divisor += 2) {
        if (num % divisor == 0) {
            return false; // 能被整除，是合数
        }
    }
    return true; // 所有除数都无法整除，是素数
}

int findNextPrime(int num) {
    if (num < 2) return 2;

    // 先定位到下一个奇数（偶数加1，奇数加2）
    int nextNum = num % 2 == 0 ? num + 1 : num + 2;
    while (nextNum <= INT_MAX) {
        if (isPrime(nextNum)) {
            return nextNum;
        }
        nextNum += 2; // 只检查奇数，跳过偶数
    }
    return -1;
}

int main() {
    int candidatePrime;
    std::string str;
    std::cin >> candidatePrime;

    const auto start = std::chrono::high_resolution_clock::now();
    const int nextPrime = findNextPrime(candidatePrime);
    const auto end = std::chrono::high_resolution_clock::now();

    std::cout << nextPrime << std::endl;
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << " nanoseconds" << std::endl;

    std::cin >> str;
    return 0;
}

修正后，不管输入什么数字，耗时都会回归合理范围，而且素数判断的结果也是正确的（比如输入65535时，会正确返回65537这个素数，而不是错误地返回65535）。

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