PAT 1015 Reversible Primes

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 (<10​5​​) 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.

Sample Input:

73 10
23 2
23 10
-2

Sample Output:

Yes
Yes
No

 大概题意:输入n,m,将n转成m进制数,并将进制数倒着转成十进制数,并判断是否是素数,只有两个数都是素数,输出Yes,否则输出No

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 1e6+5;
int prime[maxn];
int isprime[maxn];

void pri()
{
	memset(prime, 0, sizeof prime);
	memset(isprime, 0, sizeof isprime);
	for(long long  i = 2; i < maxn; i++)
	{
		if(!isprime[i])
		{
			prime[i] = 1;
			for(long long  j = i*i; j < maxn; j += i)
				isprime[j] = 1;
		}
	}
}

int main()
{
	int n, m;
	while(cin >> n)
	{
		
		if(n < 0)
			break;
		cin >> m;
		pri();
		int sum = 0;
		int a[50];
		memset(a, 0, sizeof a);
		int len = 0;
		int sum1 = n;
		while(n)
		{
			a[len++] = n%m;
			n /= m;
		}
		for(int i = 0; i < len; i++)
			sum = sum*m+a[i];
		cout << sum << endl; 
		if(prime[sum1])
		{
			if(prime[sum])
				puts("Yes");
			else
				puts("No");
		}
		else
			puts("No");
	}
	return 0;
}

 

上一篇:PAT甲级 1015 Reversible Primes 进制转化+反转+判断素数


下一篇:1015 Reversible Primes (20 分)