【PAT甲级】1015 Reversible Primes (20 分)

题意:

每次输入两个正整数N,D直到N是负数停止输入(N<1e5,1<D<=10),如果N是一个素数并且将N转化为D进制后逆转再转化为十进制后依然是个素数的话输出Yes,否则输出No。

trick:

判断转化后的数是不是1,1不是素数,如果转化后不是1说明转化前也不会是1(第一个测试点错误原因)。

AAAAAccepted code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int n,d;
 5     while(cin>>n){
 6         if(n<0)
 7             break;
 8         cin>>d;
 9         int flag=0;
10         for(int i=2;i*i<=n;++i)
11             if(n%i==0)
12                 flag=1;
13         int a[27]={0};
14         int cnt=0;
15         while(n){
16             a[++cnt]=n%d;
17             n/=d;
18         }
19         int x=0;
20         for(int i=1;i<=cnt;++i){
21             x*=d;
22             x+=a[i];
23         }
24         if(x==1)
25             flag=1;
26         for(int i=2;i*i<=x;++i)
27             if(x%i==0)
28                 flag=1;
29         if(flag)
30             cout<<"No"<<"
";
31         else
32             cout<<"Yes"<<"
";
33     }
34     return 0;
35 }
保持热爱 不懈努力 不试试看怎么知道会失败呢(划掉) 世上无难事 只要肯放弃(划掉)
原文地址:https://www.cnblogs.com/ldudxy/p/11255836.html