[백준 풀이] 1747번(소수&팰린드롬)

난이도 - 실버 1

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

 

---

 

728x90

N이 2가 아닌 짝수이면 1을 더해 홀수로 만든다.

N이상의 홀수 중 소수이면서 팰린드롬 수인 것을 찾을 때까지 반복문을 돌린다.

import java.io.*;

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

    int N = Integer.parseInt(br.readLine());
    if (N <= 2)
      bw.write("2");
    else {
      if (N % 2 == 0)
        N++;

      while (true) {
        if (isPrime(N) && reverse(N))
          break;

        N += 2;
      }

      bw.write(String.valueOf(N));
    }

    bw.flush();
    br.close();
    bw.close();
  }

  static boolean reverse(int N) {
    if (N < 10)
      return true;

    String str = String.valueOf(N);
    int len = str.length();

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

  static boolean isPrime(int n) {
    if (n < 2)
      return false;
    if (n == 2 || n == 3)
      return true;
    if (n % 2 == 0 || n % 3 == 0)
      return false;

    for (int i = 5; i * i <= n; i += 6) {
      if (n % i == 0 || n % (i + 2) == 0)
        return false;
    }
    return true;
  }
}