Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

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 (< 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.

Sample Input

73 10
23 2
23 10
-2

Sample Output

Yes
Yes
No

解答

#include <cstdio>

bool isprime(int x)
{
	if (x < 2) return 0;
	if (x == 2) return 1;
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0) return 0;
	return 1;
}

int reverse(int x, int r)
{
	int ret = 0;
	while (x) ret = ret*r + x%r, x /= r;
	return ret;
}

int main()
{
	int n, d;
	while (scanf("%d", &n), n > 0)
		scanf("%d", &d), printf("%s\n", (isprime(n) && isprime(reverse(n, d))) ? "Yes" : "No");
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论