[소수] 구하기, 판별(Kotlin)

소수: 자연수 중 1 과 자기 자신만으로 만 나누어 떨어지는 수

예) 2, 3, 5, 7, 11, 13,...

 

1. Brute Force(완전탐색)

가장 작은 소수인 2 부터 n 까지 순서대로 하나씩 판별하는 방식입니다.

판별은 2 부터 구할 값의 제곱근 까지만 순서대로 나머지값이 0인지만 알면 됩니다.

val maxNum = 100
val primes = mutableListOf<Int>()
for (i in 2..maxNum) {
    var isPrime = true
    for (j in 2..sqrt(i.toDouble()).toInt()) {
        if (i % j == 0) {
            isPrime = false
            break
        }
    }
    if (isPrime) primes.add(i)
}
println(primes.joinToString())

시간 복잡도: O( n* √(n) )

 

 

2. 에라토스테네스 체

먼저 구할 만큼의 소수를 2 부터 리스트를 만들어 놓습니다.

그리고 소수 자신의 배수는 소수가 될 수 없으니 자신의 배수를 만들어 놓은 리스트에서 제거하면 소수만 남게 됩니다.

val maxNum = 100
val isPrime = BooleanArray(maxNum + 1) { true }
isPrime[0] = false // 0은 소수가 아님
isPrime[1] = false // 1은 소수가 아님

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

val primes = (2..maxNum).filter { isPrime[it] }
println(primes.joinToString())

 

시간 복잡도: O(n log log n)

 

소수 구하는 알고리즘은 다양하지만 대표적인 2개의 알고리즘을 알아보았습니다.