[백준] 암호제작 (1837)(kotlin)

문제 설명

백준 1837번 문제 링크 알고리즘 참고

입력 및 출력

» 입력

암호 P(4 ≤ P ≤ 10100)와 K (2 ≤ K ≤ 106) 이 주어진다.

» 출력

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

예제 입출력(테스트케이스)

입력	출력
143 10	GOOD
77 12	BAD 7

문제 풀이1

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    val (P, K) = readLine().split(" ")
    val k = K.toInt()

    var pNum = BooleanArray(1_000_000) { false }
    var isGood = true
    var ans = 0

    for (i in 2 until k) {
        if (pNum[i]) continue
        if (check(i, P)) {
            isGood = false
            ans = i
            break
        }
        //Sieve of Eratosthenes(에라토스테네스의 채)
        for (j in i * 2 until k step i) pNum[j] = true
    }

    println(
        if (isGood) "GOOD"
        else "BAD $ans"
    )
}

fun check(pNum: Int, p: String): Boolean {
    var sum = 0
    for (i in p) {
        // ex) p == "143", pNum == 11(a prime number)
        // ((0 * 10) + (1 - '0')) % 11  -> (0 + 1) % 11 == 1
        // ((1 * 10) + (4 - '0')) % 11  -> (10 + 4) % 11 == 3
        // ((14 * 10) + (3 - '0')) % 11  -> (30 + 3) % 11 == 0

        // ex) p == "143", pNum == 9(not a prime number)
        // ((0 * 10) + (1 - '0')) % 9  -> (0 + 1) % 9 == 1
        // ((1 * 10) + (4 - '0')) % 9  -> (10 + 4) % 9 == 5
        // ((0 * 10) + (1 - '0')) % 9  -> (50 + 3) % 9 == 8
        sum = ((sum * 10) + (i - '0')) % pNum
    }
    return sum == 0
}