GitBook

这里写图片描述

一个数是Carmichael Numbers的条件为 1.不是素数(这个数是合数) 2.区间[2,n-1]中没有全部满足xn≡x(mod n)

求素数可用筛法 求幂可用快速幂取模

#include<stdio.h>
#include<string.h>
int prime[65200];
void getprime() {
	memset(prime,0,sizeof(prime));
	prime[0]=prime[1]=1;
	for(int i=2; i<30000; i++)
		if(!prime[i]) {
			for(int j=i*i; j<65200; j+=i)
				prime[j]=1;
		}
	return ;
}
int pow(int a,int b) {
	int MOD=b;
	long long r=1,t=a%MOD;
	while(b) {
		if(b&1)
			r=r*t%MOD;
		t=t*t%MOD;
		b>>=1;
	}
	return (int)r;
}
bool judge(int n) {
	if(!prime[n])
		return false;
	for(int i=2; i<n; i++)
		if(pow(i,n)!=i) {
			return false;
		}
	return true;
}
int main() {
	getprime();
	int n;
	while(scanf("%d",&n),n) {
		if(judge(n))
			printf("The number %d is a Carmichael number.\n",n);
		else
			printf("%d is normal.\n",n);
	}
	return 0;
}

题目地址:【UVa】[10006]Carmichael Numbers