返回目录

1）示例1：
输入：6 输出：7
2）示例2：
输入：8 输出：11
3）示例3：
输入：6789 输出：10301

Python源码

public class Solution {
    public int primePalindrome(int N) {
        while (true) {
            N = getNextPalindrome(N); // 获取>=N的回文数
            if (isPrime(N)) return N; // 判断是不是素数
            N++;
        }
    }
 
    // 获取下一个>=n的回文数
    private int getNextPalindrome(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int mid = s.length / 2;
        while (true) {
            // 制造回文数：把前半段翻转一下复制到后半段
            for (int i = 0; i < mid; i++) {
                s[s.length - 1 - i] = s[i];
            }
            // 判断制造出来的数是否>=n
            int tmp = Integer.parseInt(String.valueOf(s));
            if (tmp >= n) return tmp; // 如果>=n，返回这个造出来的数
            // 如果比n小，那前半段+1
            else {
                int j = s.length % 2 == 1 ? mid : mid - 1; // 如果是奇数长度，最靠近中轴的是s[mid]；如果是偶数长度，最靠近中轴的是s[mid-1]
                // 有9要进位（不用考虑999xxx这样首位要进位的，因为999999这个回文数肯定>=所有999xxx形式的n）
                while (s[j] == '9') {
                    s[j--] = '0';
                }
                s[j]++;
            }
        }
    }
 
    // 判断是否是素数
    private boolean isPrime(int num) {
        // 一般从2找到n/2，判断是否能被整除。从5开始，n/2>√n，这样可以减少运算量。
        if (num <= 5) {
            return num == 2 || num == 3 || num == 5;
        }

        // 从2找到√num
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

C语言源码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int primePalindrome(int N) {
    while (1) {
        N = getNextPalindrome(N); // 获取>=N的回文数
        if (isPrime(N)) return N; // 判断是不是素数
        N++;
    }
}

// 获取下一个>=n的回文数
int getNextPalindrome(int n) {
    char s[20]; // 假设最大长度为20
    sprintf(s, "%d", n);
    int len = strlen(s);
    int mid = len / 2;
    while (1) {
        // 制造回文数：把前半段翻转一下复制到后半段
        for (int i = 0; i < mid; i++) {
            s[len - 1 - i] = s[i];
        }
        // 判断制造出来的数是否>=n
        int tmp = atoi(s);
        if (tmp >= n) return tmp; // 如果>=n，返回这个造出来的数
        // 如果比n小，那前半段+1
        else {
            int j = len % 2 == 1 ? mid : mid - 1; // 如果是奇数长度，最靠近中轴的是s[mid]；如果是偶数长度，最靠近中轴的是s[mid-1]
            // 有9要进位（不用考虑999xxx这样首位要进位的，因为999999这个回文数肯定>=所有999xxx形式的n）
            while (s[j] == '9') {
                s[j--] = '0';
            }
            s[j]++;
        }
    }
}

// 判断是否是素数
bool isPrime(int num) {
    // 一般从2找到n/2，判断是否能被整除。从5开始，n/2>√n，这样可以减少运算量。
    if (num <= 5) {
        return num == 2 || num == 3 || num == 5;
    }

    // 从2找到√num
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

Java源码

import java.lang.Math;

public class Main {
    // 判断是否是素数
    private static boolean isPrime(int num) {
        if (num <= 3) {
            return num > 1;
        }
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sq = (int)Math.sqrt(num);
        for (int i = 5; i <= sq; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // 测试方法
        int num = 13; // 测试输入13
        boolean result = isPrime(num);
        System.out.println(result); // 打印结果
    }
}