5636번: 소수 부분 문자열

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

 

언어 : Kotlin

 

문제 설명 :

숫자로 이루어진 문자열이 주어진다. 이때, 부분 문자열 중에서 가장 큰 소수를 찾는 프로그램을 작성하시오.
이 문제에서는 2보다 크거나 같고, 100,000보다 작거나 같은 소수만 소수이다.

 

입력 :

입력은 여러 개의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 1,000개를 넘지 않는다.
각 테스트 케이스는 길이가 255를 넘지 않는 숫자 문자열로 이루어져 있다. 입력의 마지막 줄에는 0이 하나 주어진다.
소수 부분 문자열이 최소 하나 이상 존재하는 입력만 주어진다.

 

출력 :

각 테스트 케이스에 대해서, 가장 큰 소수 부분 문자열을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
11245 91321150448 1226406 0	11 1321 2

 

풀이 : 

에라토스테네스의 체를 사용하여 2 ~ 100,000까지의 소수를 List로 만들고 역순으로 input에 contain되는 소수가 있다면 출력하게끔 만들었다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val primes = findPrimes(100000)
    var input: String?
    while (true) {
        input = readLine()
        if (input == "0") break

        for (i in primes.lastIndex downTo 0) {
            if (input.contains(primes[i].toString())) {
                bw.write("${primes[i]}\n")
                break
            }
        }
    }

    bw.flush()
    bw.close()
}

fun findPrimes(upperLimit: Int): List<Int> {
    if (upperLimit < 2) return emptyList()

    val isPrime = BooleanArray(upperLimit + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..Math.sqrt(upperLimit.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..upperLimit step i) {
                isPrime[j] = false
            }
        }
    }

    val primes = mutableListOf<Int>()
    for (i in 2..upperLimit) {
        if (isPrime[i]) {
            primes.add(i)
        }
    }

    return primes
}