#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;
}