Carmichael Numbers

Carmichael Numbers

时间: 1ms        内存:64M

描述:

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.

提示:

参考答案(内存最优[1024]):

#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;
}

参考答案(时间最优[488]):

#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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注