526互联

回文质数(快速求出一个区间内的所有回文数)

发布时间 2023-06-20 23:04:23作者: hacker_dvd

题目链接：回文质数

code:

#include <bits/stdc++.h>

using namespace std;

vector<int> constructPalindromes(int start, int end) {
  vector<int> palindromes;

  if (start <= 1) {
    palindromes.push_back(1);
    start = 2;
  }

  int startLen = to_string(start).length();
  int endLen = to_string(end).length();

  for (int len = startLen; len <= endLen; ++len) {
    if (len % 2 == 0) {
      int halfLen = len / 2;
      int startHalf = pow(10, halfLen - 1);
      int endHalf = pow(10, halfLen) - 1;

      for (int i = startHalf; i <= endHalf; ++i) {
        string numStr = to_string(i);
        string reversed(numStr.rbegin(), numStr.rend());
        int palindrome = stoi(numStr + reversed);
        if (palindrome >= start && palindrome <= end) {
          palindromes.push_back(palindrome);
        }
      }
    } else {
      if (len == 1) {
        for (int i = start; i <= min(end, 9); ++i) {
          palindromes.push_back(i);
        }
      } else {
        int halfLen = len / 2;
        int startHalf = pow(10, halfLen - 1);
        int endHalf = pow(10, halfLen) - 1;

        for (int i = startHalf; i <= endHalf; ++i) {
          for (int mid = 0; mid <= 9; ++mid) {
            string numStr = to_string(i);
            string reversed(numStr.rbegin(), numStr.rend());
            int palindrome = stoi(numStr + to_string(mid) + reversed);
            if (palindrome >= start && palindrome <= end) {
              palindromes.push_back(palindrome);
            }
          }
        }
      }
    }
  }

  return palindromes;
}
int main() {
  int start, end;
  cin >> start >> end;
  vector<int> palindromes = std::move(constructPalindromes(start, end));
  sort(palindromes.begin(), palindromes.end());

  auto isPrime = [](int x) ->bool {
    int bound = sqrt(x);
    for (int i = 2; i <= bound; i++) {
      if (x % i == 0) {
        return false;
      }
    }
    return true;
  };
  for (int palindrome : palindromes) {
    if (isPrime(palindrome)) {
      printf("%d\n", palindrome);
    }
  }
}