알고리즘 문제를 풀다보면 심심찮게 소수 판별하는 문제를 만난다. 

요즘 알고리즘 문제 풀 때 Kotlin을 자주 사용하고 있어서 O(logN)의 시간복잡도로 소수를 판별하는 함수를 적어두려 한다.

fun isPrime(n: Int): Boolean {
    var i = 2
    while (i * i <= n) {
        if (n % i++ == 0) return false
    }
    return true
}

 이 함수의 원리는 특정 수 N의 약수들 중 중간 값은 √N 이라는 점을 이용한 것이다. 예를 들어 10의 약수는 1, 2, 5, 10인데 이 약수 중의 중간 값은 (√10) 3.162... 이다. 그래서 1부터 N까지 전부 비교하는 것이 아니라 1부터 √N 까지만 비교해서 소수를 판별할 수 있다. i <= √N 과 같이 비교할 수 있지만 루트를 사용하지 않고 비교하려면 위의 소스와 같이 양 변에 제곱을 해서 i * i <= n 으로 비교했다.

 C/C++이나 Java와 같은 for문에는 조건문을 사용할 수 있지만 Kotlin에서는 사용할 수 없으므로 while을 활용했다.