Carmichael Numbers - UVa 10006 素数判断

By | 12月16日
Advertisement

Carmichael Numbers

An important topic nowadays in computer science is cryptography. Some people even think that cryptography is the only important field in computer science, and that life would not matter at all without cryptography.  Alvaro is one of such persons, and is designing a set of cryptographic procedures for cooking paella. Some of the cryptographic algorithms he is implementing make use of big prime numbers. However, checking if a big number is prime is not so easy. An exhaustive approach can require the division of the number by all the prime numbers smaller or equal than its square root. For big numbers, the amount of time and storage needed for such operations would certainly ruin the paella.

However, some probabilistic tests exist that offer high confidence at low cost. One of them is the Fermat test.

Let a be a random number between 2 and n - 1 (being n the number whose primality we are testing). Then, n is probably prime if the following equation holds:

Carmichael Numbers - UVa 10006 素数判断

If a number passes the Fermat test several times then it is prime with a high probability.

Unfortunately, there are bad news. Some numbers that are not prime still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers.

In this problem you are asked to write a program to test if a given number is a Carmichael number. Hopefully, the teams that fulfill the task will one day be able to taste a delicious portion of encrypted paella. As a side note, we need to mention that, according to Alvaro, the main advantage of encrypted paella over conventional paella is that nobody but you knows what you are eating.

Input

The input will consist of a series of lines, each containing a small positive number n ( 2 < n < 65000). A number n = 0 will mark the end of the input, and must not be processed.

Output

For each number in the input, you have to print if it is a Carmichael number or not, as shown in the sample output.

Sample Input

1729
17
561
1109
431
0

Sample Output

The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

题意:题目提供一种筛选素数的方法,对于一个数n,如果许多2<=a<n,使得a ^n%n==a,则n有很大可能是素数。然而有些数不是素数,但是对于所有的a都满足这一点,这样的数成为Carmichael number,求给定的数是不是Carmichael number。

思路:先速筛发求素数,然后对于非素数的需要对于a利用快速幂验证。

注:最后这样的数只用15个,分别为561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,

52633,62745,63973。

AC代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int vis[65010];
void init()
{
    int i,j,k;
    for(i=2;i<=300;i++)
       if(vis[i]==0)
         for(j=i*2;j<=65000;j+=i)
         {
             vis[j]=1;
         }
}
bool check(ll a,ll n)
{
    ll k=n,f=1,ret=a;
    while(k)
    {
        if(k&1)
          f=f*ret%n;
        ret=ret*ret%n;
        k/=2;
    }
    if(f==a)
      return true;
    else
      return false;
}
int main()
{
    int n,i,j,k;
    bool flag;
    init();
    while(~scanf("%d",&n) && n>0)
    {
        if(vis[n]==0)
          printf("%d is normal.\n",n);
        else if(vis[n]==2)
          printf("The number %d is a Carmichael number.\n",n);
        else
        {
            flag=true;
            for(i=2;i<n;i++)
               if(!check((ll)i,(ll)n))
               {
                   flag=false;
                   break;
               }
            if(flag)
            {
                vis[n]=2;
                printf("The number %d is a Carmichael number.\n",n);
            }
            else
            {
                vis[n]=0;
                printf("%d is normal.\n",n);
            }
        }
    }
}

Similar Posts:

  • uva 10006 Carmichael Numbers(快速幂)

    题目链接:uva 10006 Carmichael Numbers 题目大意:判断一个数是否为Carmichael数, (非素数, 并且满足a^n % n == a, a 的取值为2 ~ n - 1). 解题思路:Eratosthenes筛选法求出素数,然后对应n如果为非素数,就对每个a进行判断,中间用到快速幂. #include <stdio.h> #include <string.h> const int N = 65005; int n, prime[N]; void ini

  • UVA - 10006 - Carmichael Numbers (快速幂+素数判断)

    题目传送:UVA - 10006 思路:就是快速幂暴力过去就行了,然后要注意点细节,就是快速幂的时候会爆int,然后就是先判断是否为素数,是素数就直接输出结果is normal,不然会超时 AC代码: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <queue> #inclu

  • Uva 10006 Carmichael Numbers(数论、快速幂、素数筛法)

    Uva 10006 Carmichael Numbers(数论.快速幂.素数筛法) 链接: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=947 题目 Time Limit:3000MS Memory Limit:0KB Description An important topic nowadays in computer science

  • UVA 10006 - Carmichael Numbers 数论(快速幂取模 + 筛法求素数)

    Carmichael Numbers An important topic nowadays in computer science is cryptography. Some people even think that cryptography is the only important field in computer science, and that life would not matter at all without cryptography. Alvaro is one of

  • UVA 10006 Carmichael Numbers(快速幂取模)

    题意: 给定一个数n,如果这个数不是素数,并且满足 (a^n)mod n = a,则这个数叫做:Carmichael Numbers. 思路: (ab) mod c = ((a mod c) * (b mod c)) mod c. 利用这个性质,二分法快速幂取模. AC代码 #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <cstdl

  • uvaoj 10006 Carmichael Numbers 快速幂取模

    uvaoj 10006 Carmichael Numbers 快速幂取模 这个题目是让判断给定的一个数是不是Carmichael Numbers,即卡米切尔数,这种数满足费马小定理,但是不是素数. 满足下面条件的数n是卡米切尔数,对于任意的a(2<=a<n)有:a^n % n = a.因为要求幂取模,所以,可以使用递归来二分,或者使用快速幂来写. 代码如下: /*******************************************************************

  • 素数判断(某公司实习生招聘笔试题目)

    设N(N >=4)为合数,则必有N = i * j; 1 < i, j < N, 不妨设 i <=j, 则有 2 <= i <= floor(sqrt(N)), 也就是说,如果N为合数,则必有因子在2到floor(sqrt(N))之间,素数判断程序如下: #include<iostream> #include<cmath> using namespace std; bool isPrime(int n) { if(n < 2) return

  • 南开百题--题目1_素数判断

    请编写一个函数jsValue(int m,int k,int xx[]),该函数的功能是:将大于整数m且紧靠m的k个素数存入数组xx传回. 最后调用函数writeDat()读取10组数据,分别得出结果且把结果输出到文件out.dat中. 部分源程序存在文件prog1.c中. 例如:若输入17 5 则应输出:19,23,29,31,37. 请勿改动主函数main()和写函数writeDat()的内容. 解题思路: 本题属于素数题.素数又称质数,是指:在一个大于1的自然数中,除了1和自身,不能被其他

  • C/C++素数判断(附exe方便不懂编程…

    在学习 python 的时候,遇到一个题目,要求用 yield 生成器来写一个判断某个范围的数是否是素数的函数,由于在编程中我们经常需要判断某个较大的数是否是素数,我提供了一种自己的解决方案,其中有点二分的思想.希望对朋友们有所帮助.判断素数的方法很多,这只是我个人的方法.由于网页功能限制,格式有可能有变化. exe下载 #include "stdafx.h" bool is_p(int argc); int _tmain(int argc, _TCHAR* argv[]) { int

  • UVA 10006 Carimichael Numbers(快速幂)

    大年初一无聊刷道题吧-.. [中文题意]给你一个整数,问你它是Carimichael Numbers还是正常数.关于那个Carimichael Numbers定义:我们把对任意的1 < x < n都有x^n恒等x(mod n)成立的合数(不是素数)n称为Carimichael Numbers. [思路分析]先用筛法预处理一遍所有数,然后再用快速幂判断就好了. [AC代码] #include<cstdio> #include<map> #include<vector

Tags: