2 hustis1403 HUSTIS1403 于 2016.02.25 21:42 提问

素数算法 ,为什么num超过int范围就会出错 ,int范围内就没问题,是a*a溢出导致的么

#include
#include
using namespace std;
typedef unsigned long long ULL;
inline bool isPrime(ULL);
inline ULL powMod(ULL a, ULL n, ULL k);
int main()
{
clock_t begin, end;
begin = clock();
ULL num=0;
for (size_t i = 0;i != 500;++i)//素数验证
{
--num;
if (isPrime(num))
cout << num << "是素数" << endl;
}
end = clock();

cout << "运行时间为:" << (double(end - begin) / CLOCKS_PER_SEC) * 1000.0 << "毫秒" << endl;
while (1);
return 0;

}

inline bool isPrime(ULL num)
{
srand((unsigned)time(NULL));
for (size_t i = 0;i != 20;++i)
if (powMod(rand()%32768+1, num - 1, num) != 1)
return false;
return true;
}

inline ULL powMod(ULL a, ULL n, ULL k)//a^n%k
{
if (n == 0)return 1;
ULL ullResult = powMod((a*a) % k, n / 2, k);
if (n % 2)
ullResult = (ullResult*a) % k;
return ullResult;
}

2个回答

devmiao
devmiao   Ds   Rxr 2016.02.25 21:53

size_t不同平台不同,32位下它相当于unsigned int,所以溢出

HUSTIS1403
HUSTIS1403 但是size_t只是用在了循环变量上,没有参与计算啊。。
接近 2 年之前 回复
li980ex
li980ex   2016.02.26 21:34

num超过int范围,a*a就会溢出,还有检查下是不是除了0

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!