이 문제에서 요소 N이 주어졌습니다. 다음 회문 소수를 찾아야 합니다.
문제 설명 − N보다 큰 회문이기도 한 가장 작은 소수를 찾아야 합니다.
회문 수는 숫자가 양방향으로 동일한 숫자입니다.
소수는 1과 자기 자신만 있는 경우의 숫자입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
N = 12
출력
101
설명
12보다 큰 일련의 회문은 22, 33, 44, 55, 66, 77, 88, 99,101… 이 중 가장 작은 회문은 101입니다.
솔루션 접근 방식
이 문제에 대한 간단한 해결책은 소수인 N보다 큰 모든 회문을 찾는 것입니다.
보다 효율적인 솔루션은 11의 배수인 짝수 팰린드롬을 찾는 것입니다.
다음은 이 솔루션의 증거입니다.
11% 11 = 0 1111% 11 = 0
이것을 사용하여 우리는 짝수 숫자의 회문을 찾을 것입니다 -
xyzzyx % 11 =0, 모든 짝수 자리를 회문이 아닌 것으로 만듭니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream>
#include <string>
using namespace std;
bool isPrime(int num) {
if (num < 2 || num % 2 == 0)
return num == 2;
for (int i = 3; i * i <= num; i += 2)
if (num % i == 0)
return false;
return true;
}
int primePalindrome(int N) {
if (8 <= N && N <= 11)
return 11;
for (int x = 1; x < 100000; ++x) {
string s = to_string(x), r(s.rbegin(), s.rend());
int y = stoi(s + r.substr(1));
if (y >= N && isPrime(y))
return y;
}
return -1;
}
int main() {
int N = 432;
cout<<"The next prime palindrome is "<<findNextPrimePallindrome(432);
return 0;
} 출력
The next number with same set of digits is 92543