소수를 판별하는 기본적인 방법
소수(prime number, 素數)는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수를 의미한다. 예를 들면 2, 3, 5, 7 ... 등이 있다. 어떤 수 \(x\)가 주어졌을 때 \(x\)가 소수인지 판별하는 가장 간단한 방법은 2부터 \(x-1\)까지 모든 수로 \(x\)를 나누었을 때 나누어 떨어지는 수가 있는지 확인하는 것이다.
// Kotlin
fun isPrime(x: Int): Boolean {
for (i in 2 until x) { // 2부터 x-1까지 반복
if (x % i == 0) return false // x가 한 번이라도 나누어 떨어지면 소수가 아님
}
return true // 모두 반복해도 나누어 떨어지지 않으면 소수
}
// Java
boolean isPrime(int x) {
for (int i = 2; i < x; i++) {
if (x % i == 0) return false;
}
return true;
}
하지만 이 방법은 \(x-1\)번의 검사를 해야 하므로 \(x\) 이하의 모든 소수를 찾아낼 때는 각 경우를 모두 검사해야 하기 때문에 굉장히 비효율적이다.
에라토스테네스의 체
에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 어떤 수 \(x\)가 주어졌을 때 \(x\) 이하의 모든 소수를 찾는 알고리즘의 구조는 다음과 같다.
- 2부터 \(x\)까지의 모든 수를 나열한다.
- 2는 소수이므로 Prime numbers에 추가하고 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 중 바로 다음인 3을 Prime numbers에 추가하고 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 중 바로 다음인 5를 Prime numbers에 추가하고 자신을 제외한 5의 배수를 모두 지운다.
- 이 과정을 계속 반복하면 \(x\)까지의 소수만 남는다.
해당 과정을 gif로 표현하면 다음과 같다.
해당 과정을 잘 보면 찾은 소수 \(p\)의 배수를 지울 때 \(p^2\)부터 시작한다는 사실을 알 수 있다. 배수를 지우는 과정에서 \(p\)의 배수 중 \(p\times (p-1)\) 까지의 모든 배수가 지워지기 때문이다. 또한 위의 경우는 \(120 < 11^2\)이기 때문에 11부터는 자기 자신만 체크하고 바로 넘어가는 것을 볼 수 있다. 다시 말해 에라토스테네스의 체로 \(x\)이하인 모든 소수를 찾을 때는 \(\sqrt{x}\)까지만 체크하면 그 뒤로 지워지지 않은 모든 수는 소수라고 볼 수 있다.
Kotlin으로 구현한 에라토스테네스의 체
val isPrime = BooleanArray(x + 1) { true } // 0부터 x까지 소수를 판별하는 배열
isPrime[0] = false
isPrime[1] = false
var i = 2
while (i * i <= x) { // 2부터 n의 제곱근까지 반복
if (isPrime[i]) {
for (j in i * i..x step i) {
isPrime[j] = false
}
}
i++
}
println("${x}이하인 소수의 개수 : ${isPrime.count { it }}") // 소수의 개수 출력
1~3번째 줄은 0부터 \(x\)까지의 소수를 판별하기 위한 Boolean
배열을 선언하면서 true로 초기화하고, 0과 1은 소수가 아니므로 false로 변경한다.
4~12번째 줄은 에라토스테네스의 체를 이용하여 소수를 판별하는 과정이다. 검사를 시작하는 \(i\)의 값을 2로 설정하고 \(i^2\)이 \(x\)이하인 모든 값에 대해 반복하여 검사를 시작한다. 6~8번째 줄에서 \(i\)가 소수인지 체크하고 소수라면 \(i^2\)부터 모든 \(i\)의 배수를 false로 변경하여 제외한다. 해당 while
문은 아래와 같이 2부터 \(\sqrt{x}\)까지 반복하는 for
문으로 바꿔도 된다.
val isPrime = BooleanArray(x + 1) { true } // 0부터 x까지 소수를 판별하는 배열
isPrime[0] = false
isPrime[1] = false
for (i in 2..sqrt(x.toDouble()).toInt()) { // 2부터 n의 제곱근까지 반복
if (isPrime[i]) {
for (j in i * i..x step i) {
isPrime[j] = false
}
}
}
println("${x}이하인 소수의 개수 : ${isPrime.count { it }}") // 소수의 개수 출력
마지막 14번째 줄에서는 \(x\)이하인 소수의 개수를 출력한다. 만약 \(x\)이하인 모든 소수를 출력하고 싶다면 반복문을 통해 isPrime 배열에서 값이 true인 인덱스를 모두 출력하면 된다.
Java로 구현한 에라토스테네스의 체
boolean[] isPrime = new boolean[x + 1];
for (int i = 2; i < isPrime.length; i++) {
isPrime[i] = true;
}
for (int i = 2; i * i <= x; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= x; j += i) {
isPrime[j] = false;
}
}
}
int c = 0;
for (int i = 2; i < isPrime.length; i++) {
if (isPrime[i]) c++;
}
System.out.println(x + "이하인 소수의 개수 : " + c);
위 Kotlin 코드를 Java 코드로 작성한 것이다. 둘 모두 동작 과정은 동일하다.
'Algorithm > 관련내용' 카테고리의 다른 글
[Kotlin] 코틀린으로 정렬 관련 문제를 풀 때 사용하는 배열이나 리스트를 정렬하는 메소드의 종류 및 각 메소드의 차이 (2) | 2023.03.31 |
---|---|
[Kotlin] 코틀린으로 알고리즘 문제를 풀 때 출력 방식별 속도에 대하여 (0) | 2023.01.20 |
투 포인터(Two Pointer) with Kotlin (0) | 2022.12.18 |
누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin (0) | 2022.12.17 |
댓글