[(코틀린)알고리즘] 소수 판별

사용 이유

n이 소수인지 판별하기 위해 사용합니다.

시간 복잡도에 따라서 다르게 구현할 수 있습니다.

---

일반적인 방법

2부터 n까지 모든 수를 체크하기 때문에 시간 복잡도 O(n)이 나오게 된다.

fun isPrime(n: Int): Boolean {
    if (n < 2) return false
    // 소수는 1과 자기 자신만 약수로 가지기 때문에
    // 만약 나누어 떨어지면 소수가 아니게 된다.
    return (2 until n).none { n % it == 0 }
}

---

위 코드에서 향상된 방법

시간 복잡도를 줄이기 위해 굳이 n까지 갈 필요 없이 루트 n 까지만 체크하면 된다.

 

12를 예시로 들어보겠다.

(곱해서 12가 되는 수는 아래만큼 있다.)

1 * 12

2 * 6

3 * 4

4 * 3

6 * 2

12 * 1

 

앞에 3개 뒤에 3개가 대칭이 되는 것을 알 수 있다.

 

이로써 우린 반만 잘라서 체크하면 되기 때문에

굳이 n까지 체크하는 것이 아닌 루트 n 까지만 체크하면 되는 것이다.

 

2부터 루트 n 까지만 루프를 돌리고 나머지는 처음 방법과 똑같이 적으면 된다.

이제 시간 복잡도가 O(√n) 까지 줄어들었다.

fun isPrime(n: Int): Boolean {
    if (n < 2) return false
    // sqrt 함수를 사용하여 루트 n을 만들었다.
    val sqrt = Math.sqrt(n.toDouble()).toInt()
    return (2..sqrt).none { n % it == 0 }
}

---

BigInteger을 사용하는 방법

자바에서 지원하는 클래스에 담긴 함수다.

BigInteger#isProbablePrime이라는 함수인데, 인자에 들어가는 숫자만큼 정확도가 갈린다.

10을 넣을 시 정확도가 0.9990234375 라고 한다.

(사실상 웬만한 수는 거의 커버가 가능한 입력 값이다.)

fun isPrime(n: Int): Boolean {
    if (n < 2) return false
    return num.toBigInteger().isProbablePrime(10)
}