Kotlin 🍬 백준 15단계 :: 4134 번

 

다음 소수

문제   |

  정수 n(0 ≤ n ≤ 4*$10^{9}$)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

 

입력   |

  첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

 

출력   |

  각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

 

 

풀이  |

  에라토스테네스의 체 알고리즘을 이용해 소수 도출 (외워두기) 6k ± 1 규칙을 이용

 

 

답안  |

fun main() {
    val count = readLine()!!.toInt()
    repeat(count) {
        val num = readLine()!!.toLong()
        val prime = nextNum(num)
        println(prime)
    }
}

fun nextNum(n: Long): Long {
    var num = n
    if (num <= 1) num = 2
    while (!isPrime(num)) {
        num++
    }
    return num
}

fun isPrime(num: Long): Boolean {
    if (num <= 1) return false
    if (num <= 3) return true
    if (num % 2 == 0L || num % 3 == 0L) return false

    var i = 5L
    while (i * i <= num) {
        if (num % i == 0L || num % (i + 2) == 0L) {
            return false
        }
        i += 6
    }
    return true
}