1. 문제 유형

• 특정 범위의 수가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우.
• ex) 자연수 N이 입력되면 1부터 N까지 소수의 개수를 출력하는 프로그램을 작성하시오.

2. 문제 접근

• 이중 for문으로 답을 찾아내는 것은 시간복잡도가 O(N^2)이며 비효율적이다.
• 에라토스테네스의 체 알고리즘을 사용하여 풀어내는 것이 효율적이다. 시간복잡도 O(N log log N)

3. 에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

4. 방법

임의의 자연수 n에 대해 그 이하의 소수를 찾는다고 가정한다. (n은 100)

• 1부터 100까지 숫자를 나열한다.
• 1은 소수가 아니므로 제외시킨다.
• 숫자 2부터 시작하며 2의 배수를 모두 제거한다.
• 같은 방식으로 3부터 시작한다.
• 4는 2의 배수를 진행할 때 제거되었음으로 넘어간다.
• 위의 과정을 반복

5. 코드 (Java)