[Algorithm] 소수와 관련된 알고리즘(feat. 에라토스 테네스의 체)

안녕하세요 Foma 💻 입니다!

 

알고리즘 문제를 풀다 보면 소수를 찾아햐 하는 유형이 많은데요.

 

소수의 갯수를 찾아야 할 때, 소수인지 아닌지 분별해야 할 때 등 효율적인 알고리즘이 필요합니다.

 

오늘은 정확히 알고 빠르게 찾기 위해서 글을 정리해보려고 합니다.

 

바로 시작할게요~!

---

기존의 소수를 찾는 방법

 

기존의 소수를 찾는 방법은 k라는 수가 있다면 단순하게 2부터 n까지 k로 나눠서 나누어 떨어지는 숫자의 갯수를 판별하면 되겠죠?

 

하지만 이런 방법은 숫자가 커지면 커질수록 비효율적이기 때문에 시간이 오래 걸리게 됩니다.

 

그러므로 효율적인 방법을 사용해야 하는데요.

---

에라토스 테네스의 체

 

먼저 2부터 n까지의 구간에서 소수의 갯수나, 어떤 소수가 있는지 확인하기 위해선 "에라토스 테네스의 체"를 알고리즘을 쓰면 됩니다.

 

찾는 방식은 아래와 같습니다.

 

1. 2부터 n까지 모든 수를 나열한다.

2. 만약 소수를 발견했다면 소수를 따로 정하고 소수의 배수를 모두 지운다.

3. 위 과정을 반복하면 구간의 모든 소수가 남는다.

 

아래 그림을 보면 이해하기 훨씬 편하실 거에요!

 

출처:위키백과

---

 

코드 구현

 

func countPrimeNumber(_ n: Int) -> Int {
    var count = 0
    var array = Array.init(repeating: false, count: n+1)
    
    for i in 2...n {
        if array[i] == false {
            count += 1
            
            for j in stride(from: i, through: n, by: i) {
               array[j] = true
            }
        }
    }
    return count
}

---

 

소수분별법

 

그 다음으로 소수인지 아닌지 빠르게 확인해야 할 때까 있습니다.

 

이러한 경우에는 "제곱근"을 이용하면 되는데요.

 

n의 약수는 무조건 n의 제곱근 안에 존재하기 때문에 2부터 sqrt(n)의 범위에서 자기 자신으로 나누어 떨어지는지 아닌지를 확인하면 됩니다.

 

주의할 점은 제곱근이 2보다 크다면 제곱근을 이용하고 아니라면 2부터 n까지 탐색해야 합니다.

---

코드 구현

 

func isPrimeNumber(_ n:Int) -> Bool {
    let sqrt = Int(sqrt(Double(n))) >= 2 ? Int(sqrt(Double(n))) : n
    for i in 2..<sqrt {
        if n%i == 0 {
            return false
        }
    }
    return true
}