在 C++ 中查找大素数：我的整数在哪里溢出？

Question

我用 C++ 编写了 Sieve of Atkin 的实现来计算大素数。它可以很好地找到第 10^8 个素数，但是当试图找到第 10^9 个素数时，我得到了不正确的结果。

看起来我正在处理整数溢出，但我不知道这是怎么可能的。我到处都在使用 uint64_t，所需的结果 (22801763489) 介于 2^34 和 2^35 之间。

我得到的结果是 1326927009。

相关代码如下：

uint64_t getPrimesAtkin(uint64_t Nn)
{
    (...)
}


int main(int argc, char** argv) {
    for (int a = 7; a < 10; a += 2)
    {
        clock_t begin = clock();
        uint64_t prime = getPrimesAtkin(pow(10,a));
        clock_t end = clock();
        printf("p(10^%d)=%12d t=%4.3f\n",a,prime, double(end - begin) / CLOCKS_PER_SEC);
    }
}

Answer 1

我没有仔细阅读你所有的代码，但是仅这一行就可以解释你的问题：

printf("p(10^%d)=%12d t=%4.3f\n",a,prime, double(end - begin) / CLOCKS_PER_SEC);

在这里，您使用 "%12d" 格式将 64 位质数传递给 printf() 函数。这种格式需要一个 int 类型的参数，而不管用于输出的位数是多少。要打印 long long（保证至少为 64 位），请使用 "ll" 修饰符 ("%12lld") 并通过转换传递素数 (long long)prime.

在 C++ 中查找大素数：我的整数在哪里溢出？

Finding a large prime in C++: where does my integer overflow?

c++

primes

integer-overflow