PAT 1015. Reversible Primes (20)

xiaoxiao2021-02-28  26

题目:1015. Reversible Primes (20)

思路:1.由于N<100000,可建立一个质数表或是写一个判断质数的函数;

            2.以N<0作为跳出循环的条件。

注意:

            在本次题目中,我选择使用质数表,但并未给0,1 标注为不是质数,导致测试点2通不过,即忽略了 reversible number 等于1的情况(如输入2,2 ,则reversible number为1)。

代码:

#include<iostream> using namespace std; int main() { //质数表 int prime[100000]={0}; for(int i=2;i<100000;++i) { if(prime[i]==0) { for(int j=2*i;j<100000;j=j+i) { prime[j]=1; } } } prime[0]=prime[1]=1; //标注1不为质数 int N,D; cin>>N; while(N>=0) { cin>>D; if(N<=1) cout<<"No"<<endl; else { if(prime[N]==0) //判断是否为质数 { int k,s=0; while(N!=0) { k=N%D; s=s*D+k; N/=D; } if(prime[s]==0) //判断反转数是否为质数 cout<<"Yes"<<endl; else cout<<"No"<<endl; } else cout<<"No"<<endl; } cin>>N; } return 0; }

转载请注明原文地址: https://www.6miu.com/read-1000108.html

最新回复(0)