Carmichael Numbers（素数判断+快速幂）
发布时间
阅读量：
阅读量
在当今计算机科学领域，密码学是一个非常重要的议题。许多人在日常生活中就已经接触到了密码技术的应用，并认为它已经渗透到了我们生活的方方面面。
Input
该输入将由一系列行组成，每一行包含一个介于2和65,000之间的正整数n。当遇到数值n=0时，则表示输入结束，并且不应进行任何处理。
Output
For every single number provided as input, you must determine whether it qualifies as a Carmichael number or not, based on the sample output.
Sample Input
Sample Output
【解析】
如果一个数不是素数并且满足 a^n modn=a ，就是Carmichael Numbers。
特别注意：a是一个随机数值，在区间2至n-2之间选取。因此要求所有位于该区间的数值都必须满足上述公式
【代码】
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
typedef long long ll;
using namespace std;
int judge(int n){//判断素数
for(int i=2;i<=sqrt(n);i++){
if(n%i==0)
return 0;
}
return 1;
}
ll power(ll a, ll b, ll p)//快速幂
{
ll ans = 1 % p, base = a;
while (b)
{
if (b & 1)
{
ans = (ans%p * base%p) % p;
}
base = base* base%p;
b >>= 1;
}
return ans;
}
int solve(int n){//判断该数是否满足公式，这一步一定要用函数写出来，不然会超时
for(int i=2;i<n;i++){
ll x=power(i,n,n);
if(x!=i){
return 0;//因为a为随机数，所以要求每一个值符合公式
}
}
return 1;
}
int main()
{
int n;
while(cin>>n&&n){
int f=0;
if(judge(n)==0){
if(solve(n)==1)
f=1;
}
if(f==1)
printf("The number %d is a Carmichael number.\n",n);
else
printf("%d is normal.\n",n);
}
return 0;
}全部评论 (0)
还没有任何评论哟~