P1217-回文质数

P1217 [USACO1.5] 回文质数 Prime Palindromes

思路

先检查是否是回文数，再检查是否是质数。
对于大于7位的数，不可能是回文质数。
除了11以外，一个数的位数是偶数的话，不可能为回文数素数。
如果一个回文素数的位数是偶数，则它的奇数位上的数字和与偶数位上的数字和必然相等，且都是偶数，所以这个数必然能被11整除。
所以8位不存在回文素数，而范围是[1, 10000000]，所以只需要检查[1, 9999999]的数即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

bool is_palindrome(int x) {
  int num[10];
  int l = 0;
  while (x > 0) {
    num[l] = x % 10;
    l++;
    x /= 10;
  }
  l--;
  for (int i = 0, j = l; i < j; i++, j--) {
    if (num[i] != num[j])
      return false;
  }
  return true;
}

bool is_prime(int x) {
  if (x % 2 == 0)
    return false;
  for (int i = 3; i <= sqrt(x); i += 2) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int a, b;
  cin >> a >> b;
  // 再大的数都不可能是回文质数
  b = min(9999999, b);
  for (int i = a; i <= b; i++) {
    if (is_palindrome(i) && is_prime(i)) {
      cout << i << endl;
    }
  }
  return 0;
}
≡