866. Prime Palindrome
Find the smallest prime palindrome greater than or equal to N.
Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.
For example, 2,3,5,7,11 and 13 are primes.
Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.
For example, 12321 is a palindrome.
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
49
50
51
52
53
| class Solution {
private:
bool isPrime(int n) {
int sqrtNum = sqrt(n);
for(int i = 2; i <= sqrtNum; i++) {
if(!(n % i))
return false;
}
return true;
}
int recursive(string num, int &len, int &N) {
if(len > num.length() * 2) {
for(int i = 0; i <= 9; i++) {
int ret = recursive(num + to_string(i), len, N);
if(ret != -1)
return ret;
}
return -1;
} else {
for(int pos = len - num.length() - 1; pos >= 0; pos--) {
num += num[pos];
}
int val = stoi(num);
if(val >= N && isPrime(val)) {
return val;
}
return -1;
}
}
public:
int primePalindrome(int N) {
if(N < 10) {
for(int i = max(N, 2); i <= 11; i++) {
if(isPrime(i))
return i;
}
return -1;
}
string num = to_string(N);
for(int len = num.length(); len <= 9; len++) {
for(int num = 1; num <= 9; num += 2) {
int ret = recursive(to_string(num), len, N);
if(ret != -1) {
return ret;
}
}
}
return -1;
}
};
|
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
| class Solution {
private:
bool isPalindrome(int n) {
string num = to_string(n);
for(int i = 0; i < num.size() / 2; i++) {
if(num[i] != num[num.size() - 1 - i])
return false;
}
return true;
}
bool isPrime(int n) {
int sqrtNum = sqrt(n);
for(int i = 2; i <= sqrtNum; i++) {
if(!(n % i))
return false;
}
return true;
}
public:
int primePalindrome(int N) {
for(int i = max(N, 2); i <= 200000000; i++) {
if(10000000 <= i && i <= 100000000)
i = 100000000;
if(isPalindrome(i) && isPrime(i))
return i;
}
return -1;
}
};
|
