首页 > 代码库 > 1702 素数判定 2

1702 素数判定 2

2024-09-16 07:03:58   216人阅读

1702 素数判定 2

 

时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
 
 
 
题目描述 Description

一个数，他是素数么？

设他为P满足(P<=263-1)

 

输入描述 Input Description

P

输出描述 Output Description

Yes|No

样例输入 Sample Input

2

 

样例输出 Sample Output

Yes

 

数据范围及提示 Data Size & Hint

算法导论——数论那一节
注意Carmichael Number

注意读入的时候不知为何必须要用cin。。。
（因为我在前面定义了 ll=long long =.= 。。。。 。。 。。
这道题主要运用费马小定律
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<ctime> 6 #define ll long long int 7 using namespace std; 8 ll n; 9 ll pd[14]={10,35,77,535,71497,2,3,5,7,11,3161};10 ll fastmul(ll a,ll b)11 {12     ll r=0;13     ll base=a;14     while(b!=0)15     {16         if(b%2!=0)17         {18             b--;19             r=(r+base)%n;20         }21         b=b/2;22         base=(base+base)%n;23     }24     return r%n;25 }26 ll fastpow(ll a,ll b)27 {28     ll r=1;29     ll base=a;30     while(b!=0)31     {32         if(b%2!=0)33         r=fastmul(r,base)%n;34         base=fastmul(base,base)%n;35         b=b/2;36     }37     return r%n;38 }39 ll check(ll n)40 {41     if(n==2)42     {43         return 1;44     }45     if(n<2&&(n%2==0))46     {47         return 0;48     }49     for(ll i=0;i<11;i++)50     {51         ll x=pd[i];52         if(x%n==0)53         continue;54         ll ans=fastpow(x,n-1)%n;55         if(ans!=1)56         return 0;57     }58     return 1;59 }60 int main()61 {62     //srand(time(0));63     scanf("%I64d",&n);64     cin>>n;65     if(check(n))66     {67         printf("Yes");68     }69     else70     {71         printf("No");72     }73     return 0;74 }

 

 

1702 素数判定 2


联系
我们