若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1543: Carmichael Numbers

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,026

题目描述

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

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 Skip 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist