(백준) (Kotlin) No. 1747 Prime Number & Palindrome

문제는 에라토스테네스의 체를 사용하여 소수 배열을 만든 다음 N을 반복하여 숫자를 검색하는 것입니다.

문자열로 변환할 때 동일하고 reversed() 함수를 실행하면 N보다 크거나 같은 가장 작은 수, 소수, 회문을 출력과 정지 루프로 얻을 수 있다.

팰린드롬은 숫자의 순서가 바뀌어도 변하지 않는 숫자입니다.

저의 경우 N의 최대값인 1,000,000을 입력하면 최대 9,999,999까지 어레이 크기를 확인할 수 있습니다.

10,000,001로 설정됩니다. 그리고 제출해서 통과했는데 생각해보니 1,111,111로 넣어도 상관없을 것 같아서 바꿔봤더니 시간이 획기적으로 줄어드는 것을 확인할 수 있었습니다.

다음은 제가 작성한 코드와 제출 결과입니다(배열 크기 = 10,000,001).

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.sqrt


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()
    var arr = IntArray(10000001){0}

    for(i in 0 .. arr.size-1){
        arr(i) = i
    }

    for(i in 2 ..Math.sqrt(arr.size.toDouble()).toInt()+1){
        if(arr(i) == 0){
            continue
        }
        for(j in i+i .. arr.size-1 step i){
            arr(j) = 0
        }
    }

    for(i in N .. arr.size-1){
        if(arr(i) == 0 || arr(i) == 1)continue
        if(arr(i).toString() == arr(i).toString().reversed()){
            println(arr(i))
            break
        }
    }


    //bw.flush()
    //bw.close()
}

다음은 제가 작성한 코드와 제출 결과입니다(배열 크기 = 1.111.111)

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.sqrt


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()
    var arr = IntArray(1111111){0}

    for(i in 0 .. arr.size-1){
        arr(i) = i
    }

    for(i in 2 ..Math.sqrt(arr.size.toDouble()).toInt()+1){
        if(arr(i) == 0){
            continue
        }
        for(j in i+i .. arr.size-1 step i){
            arr(j) = 0
        }
    }

    for(i in N .. arr.size-1){
        if(arr(i) == 0 || arr(i) == 1)continue
        if(arr(i).toString() == arr(i).toString().reversed()){
            println(arr(i))
            break
        }
    }


    //bw.flush()
    //bw.close()
}