素数生成器突然停止在 16777213

Question

我制作了一个小的 c++ 程序来检查素数。它似乎工作得很好，但过了一会儿，当它到达 16777213 时它停止了。谁能告诉我为什么？这是我的程序：

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        float div = n/float(i);
        if (!(div-floorf(div))) return false;
    }
    return true;
};

int main() {
    for(int a = 1; a < 18446744073709551614; a++ )
        if (isPrime(a))
            cout << a << endl;
    return 0;
}

Answer 1

您的程序停止打印质数，因为 floorf return 是一个 24 位精确值。因此，对于大于 2²⁴ 的任何质数 [或非质数]，计算 div - floorf(div) 将 return 为零值 [因为尾数值始终为 "the same" 对于两个值 - 尾数中的小数部分没有 space] -> 你的函数 returns false 关于数字是否为质数。

即使您移动到 double，您也会遇到同样的问题，只是更进一步。

使用整数数学，并使用 % 运算符来确定它是否被均匀分割。

如评论所述，您的代码还有其他一些问题。也要解决这些问题...

编辑：澄清一下，您的程序继续尝试计算质数。它只是发现它们都是 "not prime"，因为 float 中缺乏精度，导致 "no difference"，一旦达到精度极限。

素数生成器突然停止在 16777213

Prime number generator stops abruptly at 16777213

c++

primes