BOJ_1747 : 소수&팰린드롬

👉 문제링크

1747번: 소수&팰린드롬

---

---

🔸 문제 분석 🔸

• 소수를 구한 후 오름차순으로 팰린드롬을 찾아 출력한다.

🔸 문제 풀이 🔸

• N이 100만까지 입력되는데, 여유있게 1000만까지 소수를 구한다.
• 팰린드롬은 수를 char배열로 변환한 뒤 투포인터로 판단한다.

🔸 코드 🔸

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        final int MAX = 10_000_000;

        boolean[] pn = new boolean[MAX];
        pn[1] = true;

        for (int i = 2; i < MAX; i++) {
            if (!pn[i]) {
                int mul = 2;
                while (i * mul < MAX) {
                    pn[i * mul++] = true;
                }
            }
        }

        for (int i = N; i < MAX; i++) {
            if (!pn[i] && palindrome(i)) {
                bw.write(Integer.toString(i));
                break;
            }
        }

        bw.flush();
    }

    private static boolean palindrome(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int start = 0;
        int end = chars.length - 1;

        while (start < end) {
            if (chars[start++] != chars[end--])
                return false;
        }
        return true;
    }
}

🔸 코드 해석 🔸

• 에라토스테네스의 체로 1000만까지의 소수를 구한다.
• N이상 1000만 미만의 소수 중에서 오름차순으로 팰린드롬을 찾는다.
  • 투포인터를 이용해 판단한다.
  • 가장 먼저 발견되는 팰린드롬을 출력한다.

---

🔸 end 🔸

• 소수와 팰린드롬을 구하는 알고리즘은 아주 간단했다.
• 다만, 소수를 구하는 범위가 고민되었는데, 시간이 넉넉해서 1000만까지 여유롭게 구해도 괜찮았다.