백준 1747 소수&팰린드롬 Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

알고리즘 분류

• 수학
• 브루트 포스 알고리즘
• 정수론
• 소수 판정
• 에라토스테네스의 체

풀이

주어지는 수는 최대 100만,

그럼 최대 범위는 얼마일까?

1001001은 100만보다 크면서 가장 작은 팰린드롬이다. 하지만 소수가 아니다.

1002001은 그 다음 팰린드롬으로, 이 또한 소수가 아니다.

1003001은 그 다음 팰린드롬으로 소수다.

따라서 최대 범위는 1003001이 된다.

 

이제 에라토스테네스의 체로 1003001까지 소수인 값을 찾아놓고,

소수인 값들에 대해 팰린드롬인지 검사하고 출력하면 끝

 

최대 범위는 1000만으로 설정해도 시간 내에 답을 찾을 수 있다.

 

코드

const val MAX = 1003002
val br = System.`in`.bufferedReader()

val prime = BooleanArray(MAX)

fun makePrime(){
    prime[1]=true
    for(i in 2 until MAX){
        if(prime[i]) continue
        for(j in i*2 until MAX step i){
            prime[j]=true
        }
    }
}

fun main() = with(System.out.bufferedWriter()){

    var n = br.readLine().toInt()

    makePrime()
    
    while(true){
        if(!prime[n]){
           val str = n.toString()
           var left = 0
           var right =str.length-1
           while(left<right){
               if(str[left]!=str[right]){
                   break
               }
               left++
               right--
           }
           if(left>=right){
               write("$n")
               break
           }
       }
        n++
    }
    close()
}