Eratosthenes' Sieve
에라토스테네스의 체
* 소수 (Prime Number) : 약수가 1과 자기 자신만 존재하는 자연수
* 합성수 (Composite Number) : 소수가 아닌 수
* 통상적으로, 1은 소수가 아닌것으로 정의한다.
- 2 이상의 자연수 \(n\)이 소수인지를 \(\Theta(n)\) 시간에 찾아낼 수 있는 알고리즘이다.
(소수 판별을 Bruteforcing 방법으로 찾아낼 경우, \(\Theta(n^2)\) 시간이 소요된다.)
- \(n\)이 소수인지를 판별하기 위해,
먼저 \(2 \leq P_i \leq \lfloor\sqrt{n}\rfloor\) 인 소수 \(P_i\)들을 Bruteforcing하여 찾아낸 다음,
2 이상, \(n\) 이하의 수들 중 \(P_i\)의 배수들은 소수가 아니므로, \(P_i\)의 배수들을 지워나간다.
(이 때, \(P_i\)의 1배수는 소수이므로, 1배수들은 지우지 않고, 2배수들부터 합성수인 것으로 판별해나가야 한다.)
Mechanism (원리)
- 2 이상 \(n\) 이하의 자연수의 배열에서 소수를 가려낸다.
1. Bruteforcing(주먹구구식) 방법으로, 2 이상 \(\lfloor\sqrt{n}\rfloor\) 이하의 소수/합성수 여부 판정하기
- 소수 \(i\)는 약수가 자기자신과 1 이외는 존재하지 않는 수이므로,
2부터 \(i-1\)까지 나머지연산을 수행했을 때 나누어떨어지는 경우가 단 한번도 나오지 않아야한다.
2. 가려낸 소수들 자기 자신을 제외한, 소수들의 배수들은 모두 소수가 아닌것으로 판별해낸다.
- 이 때, 2부터 \(\lfloor\sqrt{n}\rfloor\)까지는 이미 소수/합성수 여부가 판별되어 있는 상황이므로,
배수를 지워나가는 과정은 \(\lfloor\sqrt{n}\rfloor\) 부터 \(n\) 까지의 수들을 대상으로 수행하면 된다.
Implementation (구현)
* GitHub (URL)
* C++
#include <cmath> // sqrt() Function
#include <string.h> // memset() Function
void discriminator(bool *seq, const int target)
// The size of Array 'seq' must be (sizeof(bool) * (target+1))
{
if (target < 2)
{
throw "the <size> must be 2 or larger";
return;
}
else
{
memset(seq, true, target + 1);
seq[0] = seq[1] = false;
}
bool flag; // Signal if it's a prime number
int sqrt_n = (int)sqrt(target);
for (int i = 2; i < sqrt_n + 1; i++)
{
flag = true;
for (int j = 2; j < i; j++) // Determine between 2 and √n are prime number
{
if (i % j == 0)
{
flag = false;
break;
}
}
if (flag) // If 'i' is prime number
{
for (int k = pow(i, 2); k <= target;)
{
seq[k] = false;
k += i;
}
}
}
}- \(\texttt{target}\)은 우리가 소수인지를 판별하고자 하는 2 이상의 자연수이다.
- Boolean Type Array \(\texttt{seq[]}\)의 크기는 반드시 \(\texttt{target}\)+1 이어야 한다.
(왜냐하면, 궁극적으로 얻고자하는 값이 \(\texttt{seq[target]}\) 이기 때문이다.)
Performance (성능)
* \(n\)이 소수인지 판별하는 경우
Time Complexity : \(\Theta(\sqrt{n} \times \sqrt{n}) = \Theta(n)\)
References: Wikipedia, Sieve of Eratosthenes (URL)
