Java求助,88分一个超时,求素数那块过不去

P1217 [USACO1.5] 回文质数 Prime Palindromes

chengyan @ 2023-09-09 20:02:31


import java.util.Scanner;

public class PrimePalindromesPoint {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        int a = myScanner.nextInt();
        int b = myScanner.nextInt();
        int[] palindromes = new int[b - a + 1];
        boolean[] primes = new boolean[b - a + 1];

        // 判断回文数
        for (int i = a; i <= b; i++) {
            int reversed = 0;
            int temp = i;
            while (temp != 0) {
                reversed = reversed * 10 + temp % 10;
                temp /= 10;
            }
            if (reversed == i) {
                palindromes[i - a] = i;
            }
        }

        // 从回文数中判断质数
        for (int i = 0; i < palindromes.length; i++) {
            if (isPrime(palindromes[i])) {
                primes[i] = true;
            }
        }

        // 输出结果
        for (int i = 0; i < primes.length; i++) {
            if (primes[i]) {
                System.out.println(palindromes[i]);
            }
        }
    }

    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

by chengyan @ 2023-09-09 20:03:57

我真没办法了,困住我快三个小时了,也改了两次了,大佬们帮帮忙吧qwq


by 幻想繁星 @ 2023-09-09 20:11:27

@chengyan if(1000<=x&&x<=9999||100000<=x&&x<=999999)return 0;


by 幻想繁星 @ 2023-09-09 20:12:11

@chengyan 没有长度为偶数的回文质数,证明见题解


by Li17691340595 @ 2023-09-19 01:37:49

@chengyan 把最大的那个回文质数找出来,大于他的后边就不用在判断了


|