Computer Science/Data Structures & Algorithms
[Algorithms] Eratosthenes' Sieve | 에라토스테네스의 체
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\)의..
