[Kotlin/Java] 소수 찾기와 에라토스테네스의 체

소수를 판별하는 기본적인 방법

소수(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\) 이하의 모든 소수를 찾는 알고리즘의 구조는 다음과 같다.

1. 2부터 \(x\)까지의 모든 수를 나열한다.
2. 2는 소수이므로 Prime numbers에 추가하고 자신을 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 중 바로 다음인 3을 Prime numbers에 추가하고 자신을 제외한 3의 배수를 모두 지운다.
4. 남아있는 수 중 바로 다음인 5를 Prime numbers에 추가하고 자신을 제외한 5의 배수를 모두 지운다.
5. 이 과정을 계속 반복하면 \(x\)까지의 소수만 남는다.

해당 과정을 gif로 표현하면 다음과 같다.

2부터 120까지의 소수를 찾는 에라토스테네스의 체

해당 과정을 잘 보면 찾은 소수 \(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 코드로 작성한 것이다. 둘 모두 동작 과정은 동일하다.