[C++] 소수 구하는 방법 : 에라토스테네스의 체

에라토스테네스의 체

ㅋㅋ
이름 외우기도 힘들겠지만.. 소수 구하는 방법이다.

1. 2부터 n까지 모든 자연수을 나열한다
   

2. 2를 제외한 2의 배수들을 제거한다
   

3. 2를 제외하고 남은 자연수들 중 가장 작은 수를 제외하고 그 수의 배수들을 제거한다.
   

4. 제외한거 빼고 남은 자연수 중 가장 작은 수가 n이 될 때까지 3의 과정을 반복
   

끝!

이제 남은 자연수들의 개수를 구하면 소수의 개수이다.

쉽쥬?
이렇게 하면
한 번만 순회하면 되니까 O(N)
쉬우니까 잊지말자!

---

관련 문제
https://school.programmers.co.kr/learn/courses/30/lessons/12921