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

1702 素数判定 2

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

 

直接判断??? T成狗。。。。

#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;long long n;long long  read(){    long long x=0,f=1; char ch=getchar();    while(ch<0||ch>9){if(ch==-) f=-1; ch=getchar();}    while(ch>=0&&ch<=9) {x=x*10+ch-0; ch=getchar();}    return x*f;}bool pd(long long x){    if(x==1) return false;    for(long long j=2;j*j<=x;j++)     if(x%j==0) return false;    return true;}int main(){    n=read();    if(pd(n)) printf("Yes");    else printf("No");    return 0;}

好像要用什么费马小定理的,那就过会在做吧。。。

1702 素数判定 2