✍ Kotlin으로 PS 문제 풀기
소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는Kotlin을 기반으로 작성하였습니다.
소수란?
소수는 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 수를 말합니다.
그렇다면 1은 소수일까요? 아닙니다.
1은 약수가 자기 자신 하나뿐이기 때문에 소수의 정의를 만족하지 않습니다.
소수를 판별하는 방법은?
가장 단순한 방법은 2부터 자기 자신보다 작은 수까지 하나씩 나누어 보는 것입니다.
예를 들어 어떤 수 n이 있을 때,
2, 3, 4, ... , n-1 중 하나라도 나누어떨어진다면 소수가 아닙니다.
이 방식은 최악의 경우 거의 모든 수를 확인해야 하므로
시간 복잡도는 O(N) 이 됩니다.
in Kotlin
fun main() {
val n = readln().toInt()
fun isPrime(x: Int): Boolean {
if (x <= 1) return false
for (i in 2 until x) {
if (x % i == 0) return false
}
return true
}
println(isPrime(n))
}
다만 이 방법은 비효율적입니다.
조금만 더 생각해 보면, 약수는 제곱근을 기준으로 대칭적인 구조를 가집니다.
예를 들어 36의 약수를 보면 2 × 18, 3 × 12, 4 × 9, 6 × 6처럼
어떤 약수가 존재한다면 그에 대응하는 짝도 함께 존재합니다.
즉, 어떤 수가 합성수라면 반드시 제곱근 이하의 약수 하나는 존재합니다.
따라서 2부터 √n까지만 확인해도 충분합니다.
이렇게 범위를 줄이면 시간 복잡도는
으로 크게 줄어듭니다.
import kotlin.math.sqrt
fun isPrime(x: Int): Boolean {
if (x <= 1) return false
for (i in 2..sqrt(x.toDouble()).toInt()) {
if (x % i == 0) return false
}
return true
}에라토스테네스의 체
에라토스테네스의 체는 여러 개의 소수를 빠르게 구할 때 사용하는 대표적인 알고리즘입니다.
일정 범위의 수를 배열에 저장한 뒤,
소수가 아닌 수를 차례대로 지워 나가는 방식으로 동작합니다.
예를 들어 25 이하의 소수를 구한다고 가정해 보겠습니다.
먼저 2부터 시작해서 2의 배수를 모두 지웁니다.
그다음 아직 지워지지 않은 다음 수인 3으로 넘어가서
3의 배수를 지웁니다.
이후 4는 이미 2의 배수로 지워졌기 때문에 건너뛰고,
다음 수인 5의 배수를 지웁니다.
이처럼 소수의 배수를 차례대로 지워 나가며 소수만 남기는 방법을
에라토스테네스의 체라고 합니다.
결과적으로 끝까지 지워지지 않고 남아 있는 수들이 바로 소수입니다.
코드 구현은?
구현 흐름은 다음과 같습니다.
- 먼저 범위만큼 배열을 하나 생성합니다.
- 소수를 저장할 리스트를 하나 준비합니다.
2부터 차례대로 확인합니다.- 아직 지워지지 않은 수라면 소수이므로 결과에 추가합니다.
- 그 수의 배수를 모두 지워 줍니다.
- 마지막까지 남아 있는 수들이 소수입니다.
in Kotlin
fun primeNumberSieve(): IntArray {
val nums = IntArray(1_000_001) { it }
val ret = mutableListOf<Int>()
for (x in 2 until nums.size) {
if (nums[x] == 0) continue
ret.add(nums[x])
for (y in x + x until nums.size step x) {
nums[y] = 0
}
}
return ret.toIntArray()
}위 코드에서는 0으로 바뀌지 않은 수들만 소수로 판단하여
ret 리스트에 담아 반환합니다.
다만 이 방식이 언제나 가장 좋은 방법은 아닙니다.
문제의 범위가 매우 크거나, 한 개의 수만 판별하면 되는 상황이라면
단순 소수 판별이나 다른 최적화 방법이 더 적절할 수도 있습니다.
무조건적인 정답은 아닙니다.
📌 결론
이번 글에서는 소수를 판별하는 기본적인 방법과,
여러 소수를 빠르게 구할 수 있는 에라토스테네스의 체에 대해 알아보았습니다.
정리해 보면 다음과 같습니다.
- 하나의 수가 소수인지 판별할 때는 제곱근까지만 확인하면 효율적입니다.
- 여러 개의 소수를 한 번에 구해야 할 때는 에라토스테네스의 체가 유용합니다.
- 문제의 조건에 따라 어떤 방법이 더 적합한지 판단하는 것이 중요합니다.
PS 문제를 풀다 보면 시간 복잡도를 고려해야 하는 경우가 많습니다.
소수 판별 역시 단순히 구현하는 것에서 끝나지 않고,
어떤 방식이 더 빠른지를 함께 고민하는 연습이 중요합니다.
