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

-1

我用C++编写了Sieve of Atkin的实现来计算大质数。它可以很好地找到10^8的素数，但当试图找到10^9的素数时，我得到的结果不正确。在C++中查找大素数：我的整数溢出在哪里？

它看起来像我负责的一个整数溢出，但我想不通这是怎么可能的。我在任何地方都使用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); 
    } 
}

来源

2015-07-19 wvdz

使用浮点功能（'日志（）'，'地板（）'等）似乎并不像一个非常不错的主意。 –

我不知道C++，所以这可能是无稽之谈，但是矢量的大小有限制吗？初始化筛选时，即使N + 1适合uint64_t，也许该向量的最大大小太小而无法容纳许多布尔值。 – user448810

'的printf（“P（10 ^％d）=％12D ...'我不认为'％12d'将使'printf'正确打印64位整数。尝试使用'cout'。 –

我还没有仔细阅读所有你的代码，但仅此行能解释一下你的问题：

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

在这里，您通过64比特的质使用"%12d"格式的printf()函数。无论用于输出的位数如何，此格式都需要类型为int的参数。要打印long long（保证是至少64位），使用"ll"改性剂（"%12lld"）中，用流延(long long)prime传递素。

来源

2015-07-19 20:06:25 cmaster

omg ...我一直在盯着这个小时lol。thx – wvdz

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

回答

相关问题