[Algorithm] 소수 찾기 (에라토스테네스의 체)

🖥 문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

🤔 풀이 방법

에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.

SKopp at German Wikipedia, CC BY-SA 3.0 <http://creat ivecommons.org/licenses/by-sa/3.0/>, via Wikimedia Commons

1부터 숫자 n 사이에 소수를 구하고자 할 때,

1. 0부터 n까지의 배열을 만들고 이를 모두 1로 초기화한다.
2. 0과 1은 소수가 아니므로 0으로 바꾸어준다.
3. 2는 소수이므로, 2를 제외한 2의 배수를 모두 0으로 바꾸어준다.
4. 3은 소수이므로, 3을 제외한 3의 배수를 모두 0으로 바꾸어준다.
5. 5는 소수이므로, 5를 제외한 5의 배수를 모두 0으로 바꾸어준다.
6. 7은 소수이므로, 7을 제외한 7의 배수를 모두 0으로 바꾸어준다.
7. n의 제곱근까지 위의 과정을 반복하면 모든 소수만 1로 남는다.
   위의 그림의 경우, 11^2 > 120이므로 11보다 작은 수의 배수들만 바꾸어주면 충분하다.
   즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 1로 남는 모든 수는 소수이다.

코드 설명

Int(Double(n).squareRoot())

• n의 제곱근을 구한다.
  이때, squareRoot()를 사용하기 위해선 Double형 이어야 하기 때문에 형 변환을 해주었다.

👩🏻‍💻 Swift Code

func solution(_ n:Int) -> Int {
    var sqrtN = Int(Double(n).squareRoot())
    var eratos = Array(repeating: 1, count: n + 1)
    var answer = 0

    eratos[0] = 0
    eratos[1] = 0

    for i in 0...sqrtN {
       if eratos[i] == 1 {
           var j = i * 2
           while j <= n {
               eratos[j] = 0
               j += i
           }
       }
    }

    for n in eratos {
        if n == 1 {
            answer += 1
        }
    }

    return answer
}

 

코딩테스트 연습 - 소수 찾기