[알고리즘] 소수 판별 알고리즘 - 에라토스테네스의 체

활동하는 스터디 내에서 공부한 뒤 작성된 포스트입니다.

이번 포스트에서는 소수 판별 알고리즘에 대해 간단히 작성해 보겠습니다.

소수 판별 알고리즘을 알아 보기 위해서는 소수가 무엇인지 알아보아야겠죠?

 

# 소수

소수는 1과 자기 자신 외에는 나누어떨어지지 않는 자연수로 정의됩니다.

즉, 1 과 자기 자신만을 약수로 갖는 숫자입니다.

예를 들어 5 의 약수를 찾아 보면 1 과 5 가 나옵니다. 그렇다면 5 는 소수가 되는 것입니다.

 

그럼 1 은 소수일까요?
아닙니다. 1은 자기 자신 외에 다른 약수가 없기에 소수라고 할 수 없습니다.

 

따라서 소수 판별을 하기 위해서는  1 과 자기자신을 제외한 수로 나뉘어지지 않은 수를 찾으면 됩니다.

 

# 기본 소수 판별 방법

간단히 설명해 보자면,

2 부터 자기 자신 이전까지 모든 숫자를 대입하면서 찾아가면 됩니다.

 

func isPrime(_ n: Int) -> Bool {
    if n < 2 { return false }
    for i in 2..<n {
        if n % i == 0 {
            return false  // 소수가 아님
        }
    }
    return true  // 소수임
}

이처럼 모든 수를 나누어 보고 나누어 떨어지는 수가 하나라도 있으면 소수가 아니고, 나누어 떨어지면 소수로 구분할 수 있습니다.

최악의 경우 모든 경우를 다 확인하므로 O(n) 의 시간 복잡도를 가지게 되며, 숫자가 커질 수록 비효율적임을 알 수 있습니다.

 

 

# 에라토스테네스의 체 알고리즘

특정 수의 범위에서 소수를 찾기 위한 알고리즘입니다.

풀어서 설명해 보자면,  이 방법은 특정 숫자가 소수인지 판별하는 것이 아닌, 주어진 범위 내에서 모든 소수를 효율적으로 찾아내는 알고리즘입니다.

 

각 숫자의 배수를 소거해가면서 소수를 찾는 방식으로 진행이 됩니다.

즉,  2부터 시작해, 그 배수들을 지워나가는 과정을 반복하면서 소수를 남기는 방법이지요.

 

스위프트 코드를 통해 에라토스테네스의 체 알고리즘을 알아 보겠습니다.

var isPrime = [Bool](repeating: true, count: n + 1)
isPrime[0] = false
isPrime[1] = false

Bool 타입의 배열을 생성하여 처음에는 모든 숫자를 소수로 가정하고 true로 설정합니다.

단, 0과 1은 소수가 아니므로 false로 처리합니다.

 

for i in 2...Int(Double(n).squareRoot()) {
    if isPrime[i] {
        for multiple in stride(from: i * i, through: n, by: i) {
            isPrime[multiple] = false
        }
    }
}

2 부터 시작하여 각 숫자의 배수들을 false로 설정합니다.

이때, 주어진 범위 내에서 i의 배수는 i2i^2i2부터 제거합니다. 왜냐하면 그보다 작은 배수는 이미 이전 단계에서 제거되었기 때문입니다.

 

stride(from:to:by:)를 사용해 i의 배수를 찾아가며 false로 설정합니다.

예를 들어, i가 2일 때 4, 6, 8, 10...이 소수가 아니므로 제거됩니다.

 

return (2...n).filter { isPrime[$0] }

남아 있는 true 값을 가진 숫자들, 즉 소수들을 필터링해서 반환합니다.

 

마지막으로 시간 복잡도 방면에서 알아본 뒤 포스팅을 마무리해 보겠습니다.

기본적인 소수 판별 알고리즘이 O(n) 이 걸리는 것과 비교하면, 에라토스테네스의 체는 대규모 데이터에서 매우 유리합니다.

따라서 연산의 수가 기하급수적으로 감소하게 됩니다. 입력한 값이 클 수록 시간적 이득이 극대화되기 때문입니다.

 

 

---

오늘은 소수 판별 알고리즘을 공부하며 에라토스테네스의 체 알고리즘에 대해 함께 공부해 보았습니다! ^______^