Carmichael Numbers (Uva No.10006) -- 快速幂运算_埃氏筛法_打表

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long LL;
const int maxn = 65000 + 100;

//int prime[maxn + 1];  //第i个素数,保存区间内素数 
bool is_prime[maxn];  //is_prime[i]为true表示i是素数 
bool judge[maxn];     //能随机访问某数是否为素数 

void sieve(int n) {
    memset(judge, 0, sizeof(judge));
//    int p = 0;
    for (int i = 0; i <= n; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
//            prime[p++] = i;
            judge[i] = true;
            for (int j = 2*i; j <= n; j+=i) is_prime[j] = false;
        }
    }
}

LL mod_pow(int x, int n, int mod)
{
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

bool solve(int n)
{
    for (int i = 2; i < n; i++) {
        if (mod_pow(i, n, n*10) != i)
            return false;
    }
    return true;
}

int main()
{
    int n;
    sieve(maxn);
    while (scanf("%d", &n) != EOF && n)
    {
        if (!judge[n] && solve(n)) printf("The number %d is a Carmichael number.\n", n);
        else printf("%d is normal.\n", n);
    }
    return 0;
}