首页 > 代码库 > 1015. Reversible Primes (20)(数论:素数、进制转换)
1015. Reversible Primes (20)(数论:素数、进制转换)
A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.
Now given any two positive integers N (< 105) and D (1 < D <= 10), you are supposed to tell if N is a reversible prime with radix D.
Input Specification:
The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.
Output Specification:
For each test case, print in one line "Yes" if N is a reversible prime with radix D, or "No" if not.
73 1023 223 10-2
Sample Output:
YesYesNo
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n , d; 4 static const int MAXN = 1e5 + 10; 5 bool is_prime[MAXN]; 6 int prime[MAXN]; 7 int pos = 0; 8 void Prime() 9 {10 for(int i = 2 ; i < MAXN ; ++i)11 is_prime[i] = 1;12 for(int i = 2 ; i < MAXN ; ++i)13 {14 if(is_prime[i])15 prime[++pos] = i;16 for(int j = 1 ; j <= pos ; ++j)17 {18 if(i * prime[j] >= MAXN)19 break;20 is_prime[i * prime[j]] = 0;21 if(i % prime[j] == 0)22 break;23 }24 }25 }26 int Reverse()27 {28 int sum = 0;29 do30 {31 sum = sum * d + n % d;32 n /= d;33 }while(n != 0);34 return sum;35 }36 int main()37 {38 Prime();39 while(~scanf("%d" , &n))40 {41 if(n < 0)42 return 0;43 scanf("%d" , &d);44 if(is_prime[n] && is_prime[Reverse()])45 puts("Yes");46 else47 puts("No");48 }49 }
1015. Reversible Primes (20)(数论:素数、进制转换)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。