[백준] 1747번: 소수&팰린드롬 - Kotlin[코틀린]

문제

 

1747번: 소수&팰린드롬

 

---

풀이

 

 먼저 에라토스테네스의 체를 이용해 소수 판정을 하고, whlie문을 이용해 입력받은 수보다 큰 팰린드롬 수를 찾으면 된다.

 

 에라토스테네스의 체는 소수의 배수들을 지워가면서 소수를 판정하는 것으로 다음 이미지를 보면 쉽게 이해할 수 있다.

이미지 출처 - 위키 백과

 문제에서 주어진 범위 1000000보다 큰 팬린드롬 소수는 1003001이기때문에 소수 판정은 1003001까지만 하면 된다.

 

 팰린드롬의 확인은 수를 문자열로 변환하여 확인하면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    var num = br.readLine().toInt()
    val prime = BooleanArray(1003002){ true }

    prime[1] = false
    for(i in 2 .. 1002) {
        if(!prime[i]) continue

        for(j in i*i .. 1003001 step i) {
            prime[j] = false
        }
    }

    while (true) {
        if(prime[num] && palindrome("$num")) break
        else num++
    }

    bw.write("$num")
    bw.flush()
    bw.close()
    br.close()
}

fun palindrome(num: String): Boolean {
    for(i in 0 until num.length/2) {
        if(num[i] != num[num.length-1-i]) return false
    }
    return true
}