[Baekjoon] 1747번: 소수&팰린드롬

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

문제 설명

N이 주어졌을 때 N보다 크거나 같고, 소수이면서 팰린드롬인 가장 작은 수를 출력하면 된다.

풀이 방법

이 문제는 소수 구하기와 팰린드롬 판별하기가 결합된 문제이다.

소수 구하기

에라토스테네스의 체로 구한다.

팰린드롬 판별

팰린드롬을 간단하게 판별하는 방법이 있다.

1. 숫자를 문자열로 바꾼다.
2. 문자열을 절반으로 나누어 각각 다른 변수에 저장한다.
3. 뒤쪽 문자열을 뒤집는다.
4. 뒤쪽 문자열이 앞쪽 문자열로 시작하면 그 문자는 팰린드롬이다.

예를 들어 70207이라는 숫자가 있다. 이 숫자를 절반으로 나누고 start와 end로 담는다고 치면 start에는 70, end에는 207이라는 문자열이 담긴다. 이때 end를 뒤집으면 702이고 702는 70으로 시작하기 때문에 팰린드롬이다.

 

전체 코드는 다음과 같다.

import java.io.*;

class Main {

    static boolean[] sieve;
    // 1_000_000 이상에서 가장 작은 팰린드롬 소수는 1_003_001이다.
    // 이 부분을 처리하기 위해 최댓값을 적당히 1_004_000으로 잡는다.
    static final int MAX = 1_004_000;

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

        int N = Integer.parseInt(br.readLine());

        // 1인 경우는 항상 2이다. 소수 판별을 2부터 하므로 예외처리했다.
        if (N == 1) {
            System.out.print(2);
            return;
        }

        sieve = new boolean[MAX + 1];
        setUp();
        int ans = findTarget(N);
        System.out.print(ans);
    }

    private static int findTarget(int N) {
        for (int i = N; i <= MAX; i++) {
            if (sieve[i] == false) {
                String num = String.valueOf(i);
                String start = num.substring(0, num.length() / 2);
                String end = num.substring(num.length() / 2);
                StringBuilder sb = new StringBuilder(end);
                end = sb.reverse().toString();

                if (end.startsWith(start))
                    return i;
            }
        }

        return -1;
    }

    private static void setUp() {
        for (int i = 2; i <= Math.sqrt(MAX); i++) {
            if (sieve[i] == true)
                continue;

            for (int j = i + i; j <= MAX; j += i) {
                sieve[j] = true;
            }
        }
    }
}