N보다 크거나 같은 가장 작은 소수 회문을 찾아야 한다고 가정합니다. 따라서 N이 13이면 가장 작은 회문은 101이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N이 8~11 범위에 있으면 11을 반환합니다.
-
1에서 99999 사이의 i에 대해
-
s :=i를 문자열로
-
r :=s
-
리버스 r
-
num :=인덱스 1에서 s와 r의 부분 문자열을 연결한 다음 숫자로 변환
-
num>=N이고 num이 소수이면 num을 반환
-
-
0 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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);
string r = s;
reverse(r.begin(), r.end());
int num = stoi(s + r.substr(1));
if(num >= N && isPrime(num)) return num;
}
return 0;
}
};
main(){
Solution ob;
cout << (ob.primePalindrome(105));
} 입력
105
출력
131