알고리즘(Swift) - 에라토스테네스의 체 알고리즘

에라토스테네스의 체 (Erathosthenes' Sieve)

• 소수(Prime Number)를 판별하는 알고리즘
• 자연수 N에 대해 에라토스테네스의 체 알고리즘을 수행하면 2~N 범위의 자연수는 O(1) 만에 소수인지를 판별 가능함
• 원리: 작은 수부터 시작하여 배수를 제거하는 방식으로 소수를 걸러냄
  • n의 제곱근 이하의 숫자들에 대해 반복함
  • n의 제곱근 이하의 숫자까지만 반복하는 이유
    • 어떤 수 n이 소수가 아니라면, n은 두 수의 곱으로 표현됨
    • n = a * b
    • 이때 a, b 중 적어도 하나는 루트n 이하임
    • 예를 들어 n = 36일 때
      • a = 2, b = 18 → a는 루트 36 = 6 이하
      • a = 4, b = 9 → a는 루트 36 = 6 이하
      • a = 6, b = 6 → a, b 모두 36 = 6 이하
      따라서 제곱근까지만 검사하면 n의 배수들을 모두 걸러낼 수 있음

 

알고리즘 단계

1부터 n까지 숫자 중 소수를 판별하기

 

1. 초기화

• 1부터 n까지의 모든 수를 나열함
• 예를 들어 n = 20이라면

// 0부터 n까지의 숫자를 bool 배열로 초기화
// false : 소수 아님, true: 소수
let n = 20
var isPrime = Array(repeating: true, count: n + 1)

→ isPrime 배열은 0번째 인덱스부터 20번째 인덱스까지 true로 설정됨

 

 0, 1은 소수가 아니므로 false 처리가 필요함

isPrime[0] = false // 0은 소수가 아님
isPrime[1] = false // 1은 소수가 아님

 

 

2. 소수 선택 후 해당 소수의 배수 제거

  // 2부터 n의 제곱근까지 반복
    for i in 2...Int(Double(n).squareRoot()) {
        if isPrime[i] { // 이미 false(소수 아님)인 것은 건너뜀 
            // i의 배수들을 소수가 아닌 것으로 표시
            for j in stride(from: i * i, through: n, by: i) {
                isPrime[j] = false
            }
        }
    }

• isPrime 배열에서 false인 것은 이전 수의 배수였기 때문에 false가 된 것
  • → 해당 수의 배수도 이미 false
• 첫 번째로 나온 소수 (i)를 제외하고 i * i 부터 n까지 모든 배수를 false 처리 함
• 예를 들어, i == 2일 때, 2를 제외하고 4, 6, 8, 10 … 의 수는 false
• 여기서 i를 제외한 i의 배수인데 i * 2부터 시작인 아닌 i * i부터 시작인 이유!
  • 에라토스테네스의 체 알고리즘은 i가 소수 일 때, i의 배수를 제거하는 알고리즘임
  • i * 2, i * 3… i * (i - 1)은 이미 이전에 더 작은 소수들의 배수로 제거되기 때문
  • 예를 들어 i == 5일 때, 5 * 2 = 10, 5 * 3 = 15는 이미 2, 3의 배수에서 제거 되었기 때문에 다시 확인할 필요가 없음
  • 따라서 5 * 5 = 25부터 시작해야 함

 

전체 코드

// 0부터 n까지의 숫자를 bool 배열로 초기화
// false : 소수 아님, true: 소수
let n = 20
var isPrime = Array(repeating: true, count: n + 1)
isPrime[0] = false // 0은 소수가 아님
isPrime[1] = false // 1은 소수가 아님

// 2부터 n의 제곱근까지 반복
for i in 2...Int(Double(n).squareRoot()) {
	if isPrime[i] { // 이미 false(소수 아님)인 것은 건너뜀 
		for j in stride(from: i * i, through: n, by: i) {
				isPrime[j] = false 		// i의 배수들을 소수가 아닌 것으로 표시
	   }
	}
}

→ 소수인 경우 : true, 소수가 아닌 경우: false

 

 

https://gliver.tistory.com/8

[03강] 에라토스테네스의 체 알고리즘