计算floor(n²/2)+1至n²间素数个数的C++程序结果异常求助

核心错误 #

你代码里的i^2是异或运算符，不是平方运算！C++中没有直接的平方运算符，计算平方需要用i*i，或者pow(i,2)（但pow返回浮点数，容易有精度问题，优先用i*i）。

这个错误直接导致循环范围完全错误：

• 比如i=3时，3^2的结果是1（二进制异或：11 ^ 10 = 01），所以j的起始值是(1/2)+1=1，结束值是1，循环根本不会执行，因此cnt为0，和你输出的结果一致。

次要问题 #

isPrime函数存在两个小问题：

1. 没有处理n<=1的情况，这类数不是素数，但当前函数会返回true；
2. 循环中每次调用sqrt(n)会重复计算，效率低，建议先把平方根存为整数。

修正后的代码 #

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n)
{
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    int sqrt_n = sqrt(n);
    for (int i = 3; i <= sqrt_n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}
int main() {
    int cnt=0;

    for(int i=3;i<=100;i++){
        cnt = 0;
        int square = i * i;
        int start = (square / 2) + 1; // floor(n²/2)等价于整数除法square/2
        for(int j=start; j < square; j++)
        {
            if(isPrime(j))
            {
                cnt++;
            }
        }
        cout << i << " " << cnt << endl;
    }
}

验证示例 #

以i=3为例：

• n²=9，floor(9/2)+1=4+1=5，范围是5到8
• 该区间内的素数是5、7，所以cnt=2，修正后的代码会输出3 2，符合预期。

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