[백준 Baekjoon] 1990번 소수인팰린드롬 - JAVA

[백준 Baekjoon] 1990번 소수인팰린드롬 - JAVA

---

문제 풀이

문제에서 주어진 a와 b의 범위가 최대 100,000,000 - 5로 매우 큽니다. 이렇게 큰 범위에서 소수인지 판별할 때는 에라토스테네스의 체를 사용하는 것이 효율적입니다. 다음과 같이 에라토스테네스의 체를 사용하여 소수인지 저장합니다.

public static boolean[] isPrime = new boolean[100_000_001];

public static void eratosthenes() {
    isPrime[0] = isPrime[1] = true;

    for (int i = 2; i * i <= 100_000_000; i++) {
        if (!isPrime[i]) {
            for (int j = i * i; j <= 100_000_000; j += i) {
                isPrime[j] = true;
            }
        }
    }
}

자바에서 boolean 배열은 처음 생성 시 false로 초기화 되어 true인 경우 소수가 아닌것으로 사용합니다.

 

 

다음으로는 팰린드롬인지 검사를 해야 합니다.

public static boolean isPalindrome(int n) {
    String t = String.valueOf(n);

    for (int i = 0; i < t.length() / 2; i++) {
        if (t.charAt(i) != t.charAt(t.length() - i - 1)) {
            return false;
        }
    }

    return true;
}

숫자를 문자열로 바꿔 양 끝의 수를 중앙까지 비교하여 다른 경우 false를 리턴합니다. 비교가 완료될때까지 다른 경우가 없다면 true를 리턴합니다.

 

 

효율적으로 검사하기 위해 a 이상 b 이하의 수를 소수인지 먼저 검사한 다음 팰린드롬인지 검사합니다.

for (int i = a; i <= b; i++) {
    if (!isPrime[i] && isPalindrome(i)) {
        sb.append(i).append("\n");
    }
}

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static boolean[] isPrime = new boolean[100_000_001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        eratosthenes();

        StringBuilder sb = new StringBuilder();
        for (int i = a; i <= b; i++) {
            if (!isPrime[i] && isPalindrome(i)) {
                sb.append(i).append("\n");
            }
        }
        sb.append(-1);

        System.out.println(sb);
    }

    public static boolean isPalindrome(int n) {
        String t = String.valueOf(n);

        for (int i = 0; i < t.length() / 2; i++) {
            if (t.charAt(i) != t.charAt(t.length() - i - 1)) {
                return false;
            }
        }

        return true;
    }

    public static void eratosthenes() {
        isPrime[0] = isPrime[1] = true;

        for (int i = 2; i * i <= 100_000_000; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= 100_000_000; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }
}