[파이썬, 자바] 백준 - 1747 (에라토스테네스의 체)

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

 

이 문제는 소수 판별과 팰린드롬 판별만 할 수 있으면 쉽게 풀 수 있다.

 

<문제 풀이>

1. 소수를 판별한다.

  - 문제에서 주어진 N보다 큰 수가 팰린드롬일 수 있기 때문에 N의 최댓값보다 더 큰 범위의 소수를 판별해야 한다.

 

2. 팰린드롬을 구한다.

 - 숫자를 문자로 바꾸는 방법만 알면 된다.

 

구체적인 메커니즘은 주석으로 자세히 달아놨다.

 

Code(Python)

import sys
input = sys.stdin.readline

N = int(input())
maxN = 2000000
sosu = [False, False] + [True] * (maxN - 1)

# 소수 판별
# False : 소수 X
# True : 소수 O
for i in range(int(maxN**0.5) + 1): # 구하고자 하는 최대 수의 제곱근까지만 반복
    if sosu[i]:
        for j in range(2*i, maxN + 1, i): # 현재 소수의 배수들은 모두 소수가 아닌 것으로 처리
            sosu[j] = False
         
# 팰린드롬 판별   
for i in range(N, len(sosu)):
    if sosu[i]: # 현재 수(i)가 소수라면
        target = str(i) # 소수 -> 문자열 변환
        if target == target[::-1]: # 현재 문자열과 반대로 뒤집은 문자열이 같으면 팰린드롬이므로
            print(i) # 출력 후
            break # 반복문 탈출 -> 프로그램 종료

 

Code(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj_1747 {

    static int N;
    static int limit = 2000000; // N보다 큰 펠린드롬을 구해야 하기 때문에 N의 최댓값보다 크게 범위를 확장해 소수를 구해야 한다.
    static boolean[] isPrime = new boolean[limit + 1]; // 늘린 범위에 맞춰 소수 판별 리스트 초기화

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

        erato(); // 소수 구하기

        palindrome(); // 펠린드롬 출력
    }

    /**
     * 펠린드롬 출력 함수
     */
    private static void palindrome() {
        for (int i = N; i < limit + 1; i++) {
            if (!isPrime[i] & isPalindrome(i)) { // 현재 숫자가 소수이면서 동시에 펠린드롬이라면
                System.out.println(i); // 출력하고
                break; // 반복문 탈출 -> 프로그램 종료
            }
        }
    }

    /**
     * 펠린드롬 판별 함수
     */
    private static boolean isPalindrome(int i) {
        String num = String.valueOf(i); // 파라미터로 받은 수를 문자열로 변환(한 자릿수 단위로 비교해야 하기 때문)

        int mid = num.length() / 2; // 숫자의 절반까지만 가도 펠린드롬을 판별할 수 있기 때문에 숫자의 절반 인덱스 계산
        for (int j = 0; j < mid; j++) {
            if (num.charAt(j) != num.charAt(num.length() - 1 - j)) { // 펠린드롬이 아니라면
                return false; // false 반환
            }
        }
        return true; // 무사히 for문을 탈출했다면 펠린드롬이므로 true 반환
    }

    /**
     * 소수 판별 함수
     */
    private static void erato() {
        /**
         * false -> 소수 O
         * true -> 소수 X
         */
        isPrime[0] = isPrime[1] = true; // 0과 1은 소수가 아니므로 소수가 아닌 것으로 처리

        for (int i = 2; i < Math.sqrt(limit) + 1; i++) { // 구할 소수의 최대 범위의 제곱근까지만 반복
            if (isPrime[i]) { // 현재 수가 소수가 아니라면
                continue; // 다음 수로 넘어가
            }

            // 현재 수가 소수라면
            for (int j = i * i; j < limit + 1; j += i) { // 구할 소수 최대 범위까지 가면서
                isPrime[j] = true; // 현재 수의 배수들을 소수가 아닌 것으로 처리
            }
        }
    }

}