[백준] 1929번 소수구하기 JAVA

1929번 소수구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

3 16

출력

3
5
7
11
13

설명

1. 소수를 구하는 방법 중 에라토스테네스 체를 사용
2. 알고리즘 시간 복잡도 : O(NlogNlogN)
3. 에라토스테네스의 체는 다수의 소수를 찾을 때 효과적
4. 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.
5. 소스코드