[백준 1747] 소수&팰린드롬 with JAVA

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

 

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        if (n == 1){
            System.out.println(2);
            System.exit(0);
        }
        for (int i = n; ; i++){
            if (isPalind(i) && isPrime(i)){
                System.out.println(i);
                System.exit(0);
            }
        }
    }
    public static boolean isPrime(int x){
        for (int i = 2; i <= Math.sqrt(x); i++){
            if (x % i == 0){
                return false;
            }
        }
        return true;
    }
    public static boolean isPalind(int x) {
        String strX = Integer.toString(x);
        int cnt = strX.length();
        for (int i = 0; i <= cnt / 2; i++){
            if (strX.charAt(i) != strX.charAt(cnt-i-1)){
                return false;
            }
        }
        return true;
    }
}

 

수학을 모르면 풀기 힘든 문제이다.

1은 소수가 아님을 간과해서, 한 번 실패했다.

 

isPrime은 소수를 판정해주는 함수

isPalind는 팰린드롬을 판정해주는 함수

 

isPrime :

에라토스테ㅇ네스의 체를 사용하는 방법이 가장 빠르다.

소수는 자기 자신의 제곱근보다 작은 소수들에게 나눠떨어지지않음을 이용한다.

 

isPalind :

int를 문자열로 바꿔줘야 구현하기 편하다.

문자열의 길이가 홀수여도 중간 글자는 펠린드롬 여부에 영향을 끼치지 않기 때문에 짝수, 홀수 구분할 필요가 없다.

for문을 cnt/2까지로 제한하지 않으면 중복으로 검사하기 때문에 속도가 느려진다. (백준사이트 내 시간 여부에는 상관이 없는 듯 하다.)

 

펠린드롬을 판정하는 함수가 소수를 판정하는 함수보다 훨씬 빠르기 때문에

isPalind && isPrime 의 조건문이 isPrime && isPalind 의 조건문보다 당연히 빠를 것이다.