问题描述

素数算法 ，为什么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;
}

解决方案

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

解决方案二：

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