题目描述
Certain cryptographic algorithms make use of big prime numbers. However, checking whether a big number is prime is not so easy. Randomized primality tests exist that offer a high degree of confidence of accurate determination at low cost, such as the Fermat test. Let a be a random number between 2 and n – 1, where n is the number whose primality we are testing. Then, n is probably prime if the following equation holds: an mod n = a If a number passes the Fermat test several times, then it is prime with a high probability. Unfortunately, there is bad news. Certain composite numbers (non-primes) still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers. Write a program to test whether a given integer is a Carmichael number.
输入
The input will consist of a series of lines, each containing a small positive number n ( 2 < n < 65, 000). A number n = 0 will mark the end of the input, and must not be processed.
输出
For each number in the input, print whether it is a Carmichael number or not as shown in the sample output
样例输入
1729
17
561
1109
431
0
样例输出
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.
参考代码
#include"stdio.h"
#define m 70000
int prime[m];
void p()
{
int i,j;
prime[1]=1;
for (i=2;i<=m/2;i++)
{
if(!prime[i])
{
for (j=i+i;j<m;j+=i)
prime[j]=1;
}
}
}
long long carm(long long a,long long n)
{
long long mm=n,t=1;
while(mm)
{
if(mm%2==1)
t=((a%n)*(t%n))%n;
mm=mm/2;
a=((a%n)*(a%n))%n;
}
return t;
}
int main()
{
long long n,i,flag;
p();
while(scanf("%lld",&n)&&n)
{
flag=1;
if(prime[n])
{
for (i=2;i<n;i++)
{
if(carm(i,n)!=i)
{
flag=0;
break;
}
}
}
if(flag&&prime[n])
printf("The number %lld is a Carmichael number.n",n);
else
printf("%lld is normal.n",n);
}
return 0;
}
解析
暂无
