![](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FuVpvY%2Fbtq2M1qfX3e%2FJLyD68n7R5ZfdS780fOjHk%2Fimg.png)
Computer Science/Data Structures & Algorithms
[Algorithms] Eratosthenes' Sieve | 에라토스테네스의 체
Eratosthenes' Sieve 에라토스테네스의 체 * 소수 (Prime Number) : 약수가 1과 자기 자신만 존재하는 자연수 * 합성수 (Composite Number) : 소수가 아닌 수 * 통상적으로, 1은 소수가 아닌것으로 정의한다. - 2 이상의 자연수 n이 소수인지를 Θ(n) 시간에 찾아낼 수 있는 알고리즘이다. (소수 판별을 Bruteforcing 방법으로 찾아낼 경우, Θ(n2) 시간이 소요된다.) - n이 소수인지를 판별하기 위해, 먼저 2≤Pi≤⌊√n⌋ 인 소수 Pi들을 Bruteforcing하여 찾아낸 다음, 2 이상, n 이하의 수들 중 Pi의..