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.
Example 1:
Input: 6
Output: 7
Example 2:
Input: 8
Output: 11
Example 3:
Input: 13
Output: 101
Note:
1 <= N <= 10^8- The answer is guaranteed to exist and be less than
2 * 10^8.
solution1:timeout?
public int primePalindrome(int N) {
while(!isPrimePalindrome(N))
N++;
return N;
}
public boolean isPrimePalindrome(int n){
int n0 = n;
if(n == 1) return false;
for(int i = 2; i <= n / 2; i++){
if(n % i == 0)
return false;
}
List<Integer> list = new ArrayList<>();
while(n0 > 0){
list.add(n0 % 10);
n0 /= 10;
}
for(int i = 0; i <= list.size() / 2; i++){
if(!(list.get(i) == list.get(list.size()-i-1)))
return false;
}
return true;
}
solution2
class Solution {
public int primePalindrome(int N) {
while(true){
if(isPrime(N) && isPalindrome(N))
return N;
N++;
if (10_000_000 < N && N < 100_000_000)
N = 100_000_000;
}
}
public boolean isPrime(int n){
if(n == 1) return false;
int middle =(int) Math.sqrt(n);
for(int i = 2; i <= middle; i++){
if(n % i == 0)
return false;
}
return true;
}
public boolean isPalindrome(int n){
int n0 = n;
int n1 = 0;
while(n > 0){
n1 = n1 * 10 + n % 10;
n = n / 10;
}
if(n1 == n0)
return true;
return false;
}
}
判断是否为回文的时候，根据回文的性质，构造一个新的数和原来的数比较是否相等
同时注意一个性质，当N∈（107,108）时，N一定不是回文数，所以就直接跳过
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
