[JAVA] 백준 1747 에라토스테네스의 체

 

 

 

 

1747번: 소수&팰린드롬

문제

어떤 수 N이 주어졌을 때 N보다 큰 소수이면서 팰린드롬인 수 중 가장 최소값을 출력하시오.

풀이

에라토스테네스의 체

        // 1,000,000이 값으로 들어왔을 때 소수이면서 팰린드롬인 수 중 가장 최소값 1003001
        boolean[] A = new boolean[1003002];
        for(int i=2; i<Math.sqrt(A.length); i++){
            if(A[i]) continue;
            for(int j = i + i; j<A.length; j += i){
                A[j] = true;
            }
        }

소수 배열의 크기는 1,000,000이 들어왔을 때 소수이면서 팰린드롬인 수 중 가장 최소값인 1003001을 포함하도록 만들었다.

팰린드롬 검사

public static boolean isPalindrome(int num){
        String number = String.valueOf(num);
        String reverse = new StringBuilder().append(num).reverse().toString();

        if(number.equals(reverse)) return true;
        else return false;
    }

기존의 숫자 number값과 StringBuilder로 reverse한 숫자를 비교하여 같으면 true를 출력하였다.

검사

        // N이 1이라면 1을 제외시켜야함.
        for(int i = N > 1 ? N : 2; i<A.length; i++){
            if(!A[i] && isPalindrome(i)){
                System.out.println(i);
                break;
            }
        }

1은 소수가 아니기때문에 제외시켜줘야한다.

즉, N에 1이 들어왔을 때 2부터 시작하도록 해주었다.

전체 코드

import java.io.IOException;
import java.util.Scanner;

class Main {
    public static void main(String[] args) throws IOException {

        int N = new Scanner(System.in).nextInt();

        // 에라토스테네스의 체
        // 1,000,000이 값으로 들어왔을 때 소수이면서 팰린드롬인 수 중 가장 최소값 1003001
        boolean[] A = new boolean[1003002];
        for(int i=2; i<Math.sqrt(A.length); i++){
            if(A[i]) continue;
            for(int j = i + i; j<A.length; j += i){
                A[j] = true;
            }
        }

        // N이 1이라면 1을 제외시켜야함.
        for(int i = N > 1 ? N : 2; i<A.length; i++){
            if(!A[i] && isPalindrome(i)){
                System.out.println(i);
                break;
            }
        }

    }

    public static boolean isPalindrome(int num){
        String number = String.valueOf(num);
        String reverse = new StringBuilder().append(num).reverse().toString();

        if(number.equals(reverse)) return true;
        else return false;
    }

}

결과