[백준 1747번] [Kotlin] 소수&팰린드롬

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

1747번: 소수&팰린드롬

 

난이도 : 실버 1
태그 : 수학, 브루트포스 알고리즘, 정수론, 소수 판정, 에라토스테네스의 체

 

 

설명

소수이면서, 동시에 팰린드롬인 수를 찾는 문제입니다.

팰린드롬은 그냥 단순히, 문자열을 뒤집었을 때 같은 문자열 (ex> 토마토, 기러기)을 팰린드롬이라고 합니다.

 

 

해당 문제에서는 에라토스테네스의 채가 유용하게 쓰일 것 같네요.

 

에라토스테네스의 채?

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

에라토스테네스의 채는 간단히 말하자면,

소수인지 아닌지를 체크할 배열을 만들어 두고, true로 초기화 합니다.

 

소수인 2의 배수인 4, 6, 8, 10 ...은 어짜피 모두 소수가 아닙니다. 따라서, 4, 6, 8, 10을 false로 처리합니다.

이후, 다음 소수인 수(true)를 만납니다. 3이네요. 3의 배수는 어짜피 모두 소수가 아닙니다. 6, 9, 12, 15, ... 를 모두 처리 합니다.

4는 false이니 건너뜁니다. 다음 true인 수(소수)를 봅시다. 5네요.

5는 소수이며, 5의 배수는 역시나 소수가 아닙니다. 10, 15, 20, 25, 30, 35 ...를 false 처리 합니다.

이를 계속 반복해나가며 소수를 추려내는 방식입니다.

 

 

 

소스코드

import kotlin.math.sqrt

fun main() {
    var n = readln().toInt()

    val isPrime = BooleanArray(1004002) { true }

    for(i in 2 ..sqrt(1004001.0).toInt()) {
        if(isPrime[i]) {
            for(j in i * 2 .. 1004001 step i) {
                isPrime[j] = false
            }
        }
    }
    isPrime[0] = false
    isPrime[1] = false

    while(true) {
        if(isPrime[n] && n.toString() == n.toString().reversed()) {
            println(n)
            break
        }
        n++
    }
}

 

n의 범위는 1<= n <= 1,000,000 이므로 가장 큰 n은 1,000,000 이며, 그 다음으로 큰 소수 & 팰린드롬 수는 1,004,001 입니다.

따라서 isPrime 배열의 크기는 1,004,002 으로 초기화합니다.

 

이후 에라토스테네스의 채를 적용시켜 소수를 추려낸 뒤,

숫자를 문자열로 바꾸고, 이를 뒤집은게 뒤집지 않은 문자열과 같다면 이를 출력합니다.

 

 

후기

에라토스테네스의 채는 소수 판정 문제에서 꽤 자주 등장하는 알고리즘입니다.

이 기회에 한 번 사용법을 제대로 익혀두면 나중에 꽤나 유용하게 쓰입니다.