[Data Structure / Algorithms] 에라토스테네스의 체 (Sieve of Eratosthenes)

전성훈·2023년 11월 3일

Algorithms baekjoon iOS programmers swift

Data Structure-Algorithm

목록 보기

10/35

주제: 전체 수의 범위 안에서 존재하는 모든 소수를 찾아야 할 때

정의

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다.
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.
에라토스테네스의 체 알고리즘은 다음과 같다.
1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

에라토스테네스의 체

그림의 경우, $11^2>120$ 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

구현

에라토스테네스의 체를 활용해서 n까지의 모든 소수 출력하기

에라토스테네스의 체 알고리즘을 이용하여 1부터 N까지의 모든 소수를 출력하는 프로그램을 작성하면 다음과 같다.
매 스텝마다 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다고 하였으나, 이때 i 는 N의 제곱근(가운데 약수)까지만 증가시켜 확인하면 된다.
그리고 가끔식 문제에서 1이 소수인지 판별해야 하도록 입력 조건이 주어질 수 있는데, 1은 소수가 아니므로 그런 경우에는 다음 소스코드에 array[1]의 값으로 false를 넣어주는 부분을 추가해주면 된다.

import Foundation

let n = 1000
// 처음에는 모든 수가 소수(true)인 것으로 초기화 (0과 1은 제외)
var array = [Bool](repeating: true, count: n + 1)

// 에라토스테네스의 체 알고리즘 
for i in 2..<Int(sqrt(Double(n))) + 1 {  // 2부터 n의 제곱근까지의 모든 수를 확인하며 
	if array[i] == true {  // i가 소수인 경우
		// i를 제외한 i의 모든 배수 지우기
		var j = 2 
		while i * j <= n { 
			array[i * j] = false
			j += 1 
		}
	}
}

// 모든 요소 출력 
for i in 2...n { 
	if array[i] == true { 
		print(i, terminator: " ")
	}
}

프로그레머스 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예

n	result
10	4
5	3

입출력 예 설명
- 입출력 예 #1
- 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
- 입출력 예 #2
- 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

풀이

import Foundation 

func solution(_ num: Int) -> Int { 
    var count = 0 
    var array = [Bool](repeating: true, count: num + 1)
    
    // 에라토스테네스의 체
    for i in 2..<Int(sqrt(Double(num))) + 1 { 
        if array[i] == true { 
            var j = 2 
            while (i * j) <= num { 
                array[i * j] = false
                j += 1
            }
        }
    }
    
    
    for i in 2...num { 
        if array[i] == true { 
            count += 1
        }
    }
    
    return count 
}

백준 주어진 숫자 중 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.

에라토스테네스 체를 활용한 풀이

import Foundation

var count = 0

//let numCount = Int(readLine()!)!
//let numArray = readLine()!.components(separatedBy: " ").map { Int($0)! }

let numCount = 4
let numArray = [1,3,5,7]

let numArrayMaxValue = numArray.max()!

var checkCount = [Bool](repeating: true, count: numArrayMaxValue + 1)

for i in 2..<Int(sqrt(Double(numArrayMaxValue))) + 1 {
   if checkCount[i] == true {
       var j = 2
       while(i * j) <= numArrayMaxValue {
           checkCount[i * j] = false
           j += 1
       }
   }
}

checkCount[0] = false
checkCount[1] = false

for num in numArray {
    if checkCount[num] == true {
        count += 1
    }
}

print(count)