Prime Palindrome trong C++

Tìm số nguyên tố đối xứng (palindrome) nhỏ nhất ≥ N.

Ví dụ: N=13 → 101.

Giải pháp: sinh palindrome lẻ (bằng cách gương chuỗi số i, bỏ ký tự đầu khi gương) và kiểm tra nguyên tố.

• Nếu 8≤N≤11 trả về 11 (trường hợp đặc biệt)

• For i=1..99999:
  s = to_string(i), r = reverse(s)
  num = stoi(s + r.substr(1)) (palindrome lẻ độ dài chẵn)
  Nếu num≥N và isPrime(num) → return num

• isPrime: kiểm tra chia hết đến sqrt(n)

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    bool isPrime(int n){ if(n%2==0 && n>2) return false; for(int i=3;i*i<=n;i++) if(n%i==0) return false; return n!=1 && n!=0; }    int primePalindrome(int N) {       if(8<=N && N<=11) return 11;       for(int i=1;i<100000;i++){ string s=to_string(i), r=s; reverse(r.begin(),r.end()); int num=stoi(s+r.substr(1)); if(num>=N && isPrime(num)) return num; } return 0; } }; int main(){ Solution ob; cout << ob.primePalindrome(105); }

Đầu vào

105

Đầu ra

131