教你如何建设网站,网页浏览器的缩写,建设者网站,西安网站建设熊掌号本题目使用费马定理时#xff0c;我随机定义了10个数字#xff0c;循环用费马小定理判断#xff0c;数组中的值不用和我的相同#xff0c;随机即可。
#include iostream
using namespace std;
typedef unsigned long long ll;
bool isPrime[65007];
ll a[10];
voi…本题目使用费马定理时我随机定义了10个数字循环用费马小定理判断数组中的值不用和我的相同随机即可。
#include iostream
using namespace std;
typedef unsigned long long ll;
bool isPrime[65007];
ll a[10];
void initA()
{a[0] 33;a[1] 97;a[2] 65;a[3] 42;a[4] 61;a[5] 74;a[6] 1000;a[7] 1500;a[8] 10000;a[9] 3222;
}
void sieve()
{for (int i 0; i 65000; i){isPrime[i] true;}isPrime[0] false;isPrime[1] false;for (int i 1; i * i 65000; i){if (!isPrime[i]){continue;}for (int j 2 * i; j 65000; j i){isPrime[j] false;}}
}
ll mulMod(ll a, ll b, ll mod)
{ll res 0;while (b){if (b 1){res (res a) % mod;}a (a 1) % mod;b b 1;}return res;
}
ll powMod(ll a, ll b, ll mod)
{ll res 1;while (b){if (b 1){res mulMod(res, a, mod);}a mulMod(a, a, mod);b b 1;}return res;
}
bool fermet(int p)
{ll n p;for (int i 0; i 10; i){int powNumber powMod(a[i], n, n);if (powNumber ! (a[i] % n)){return false;}}return true;
}
bool judgeVal(int p)
{return fermet(p) !isPrime[p];
}
int main()
{initA();sieve();int p 0;while (true){scanf(%d, p);if (p 0){break;}if (judgeVal(p)){printf(The number %d is a Carmichael number.\n, p);}else{printf(%d is normal.\n, p);}}return 0;
}
