'에라토스테네스의 체' 란?
'에라토스테네스의 체'란, 2부터 시작하는 양의 정수들 중에서 소수(prime number)인 것을 찾아내는 알고리즘 중 하나입니다.
이 알고리즘은 2부터 시작하여, 그 다음 소수의 배수를 모두 지워가면서 소수를 찾아내는 방식으로 동작합니다.
먼저, 2부터 n까지의 모든 정수를 배열에 저장합니다. 그리고 배열에서 2를 제외한 2의 배수를 모두 지웁니다. 다음으로, 배열에서 3을 제외한 3의 배수를 모두 지웁니다. 이렇게 배열에서 지워지지 않은 가장 작은 수를 다음 소수로 간주하고, 그 수를 제외한 그 수의 배수를 모두 지웁니다. 이 과정을 반복하여, 배열에서 지워지지 않은 수가 소수가 됩니다.
예를 들어, 2부터 10까지의 소수를 찾는 과정을 살펴보겠습니다.
먼저, 2를 제외한 2의 배수를 모두 지웁니다. 따라서 2, 3, 5, 7, 9가 남게 됩니다.
다음으로, 3을 제외한 3의 배수를 모두 지웁니다. 따라서 2, 3, 5, 7가 남게 됩니다.
다음으로, 5를 제외한 5의 배수를 모두 지웁니다. 따라서 2, 3, 5, 7가 남게 됩니다.
마지막으로, 7을 제외한 7의 배수를 모두 지웁니다. 따라서 2, 3, 5, 7이 남게 됩니다.
따라서, 2부터 10까지의 소수는 2, 3, 5, 7입니다.
에라토스테네스의 체 알고리즘은 비교적 간단하고 직관적으로 이해할 수 있습니다. 또한, 소수를 찾는 데에 걸리는 시간 복잡도가 상대적으로 작아서, 대부분의 경우에 빠른 속도로 소수를 찾아낼 수 있습니다.
에라토스테네스의 체 알고리즘 구현
에라토스테네스의 체 알고리즘은 크게 두 가지 과정으로 이루어진다. 첫 번째 과정은 배열에 소수인지 아닌지를 체크하는 것이고, 두 번째 과정은 찾은 소수를 기반으로 주어진 범위 내의 소수들을 출력하는 것이다.
C언어를 기반으로 에라토스테네스의 체 알고리즘을 구현하려면, 우선 다음과 같이 코드를 작성해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void Sieve_of_Eratosthenes(int* arr, int n) {
// arr : 배열
// n : 찾고자 하는 수 중 가장 큰 값
// 초기화
for (int i = 2; i <= n; i++) {
arr[i] = i;
}
// 에라토스테네스의 체 알고리즘
for (int i = 2; i * i <= n; i++) {
if (arr[i] == 0) continue;
for (int j = i * 2; j <= n; j += i) {
arr[j] = 0;
}
}
}
|
cs |
위 코드에서는 먼저 배열을 초기화한 다음, 에라토스테네스의 체 알고리즘을 이용하여 소수를 찾는다. 이를 위해, 배열의 인덱스를 찾고자 하는 수로 초기화한 후, 에라토스테네스의 체 알고리즘을 적용한다.
에라토스테네스의 체 알고리즘의 핵심은, 소수의 배수를 모두 지워나가는 것이다. 따라서, 2부터 시작하여 2의 배수를 모두 지우고, 3부터 시작하여 3의 배수를 모두 지우는 과정을 반복하면서 소수를 찾아낸다. 이 때, 배열의 값이 0인 경우는 이미 지워진 수이므로, 무시하고 다음 인덱스로 넘어간다.
|
1
2
3
4
5
6
7
8
9
10
|
int main() {
int n = 100;
int arr[101] = { 0, };
Sieve_of_Eratosthenes(arr, n);
for (int i = 2; i <= n; i++) {
if (arr[i] != 0) printf("%d ", arr[i]);
}
return 0;
}
|
cs |
위와 같이, 소수를 찾고자 하는 범위 내에서 Sieve_of_Eratosthenes() 함수를 호출하고, 반환된 배열을 이용하여 소수를 출력한다.
에라토스테네스의 체 알고리즘의 시간 복잡도
에라토스테네스의 체 알고리즘의 시간 복잡도는 O(n log log n)입니다.
이 알고리즘의 주요 연산은 반복문에서 배열에서의 연산이므로, 전체적인 시간 복잡도는 배열의 크기인 n에 비례합니다. 이 중요한 연산은 i^2부터 n까지의 범위에서, i가 소수일 때만 진행되므로 전체적인 연산의 횟수는 log log n에 비례합니다. 따라서 전체적인 시간 복잡도는 O(n log log n)으로 계산할 수 있습니다.
시간 복잡도가 비교적 작으므로, 이 알고리즘은 대부분의 경우에 빠른 속도로 소수를 찾아낼 수 있습니다.