UVA 10006 埃氏筛法+快速幂

本题目使用费马定理时，我随机定义了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;
}