https://www.acmicpc.net/problem/1929
문제 설명에 에라토스테네스의 체로 풀어보자고 써있길래, 에라테네스의 체를 인터넷에 검색해봤다.
에라토스테네스의 체
에라토스테네스의 체의 이름에 맞게 체로 숫자들을 거른다. 2부터 시작해서 구하고자 하는 구간까지
2를 제외한 2의 배수, 3을 제외한 3의 배수, 5를 제외한 5의 배수... 이런식으로 숫자들을 거르다가
구간의 마지막 수가 소수의 제곱보다 작거나 같으면 반복을 종료한다. 이 때 제외된 숫자들이 소수이다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
final int MAX_VALUE = 1000000;
Scanner sc = new Scanner(System.in);
int start = sc.nextInt();
int end = sc.nextInt();
boolean[] prime = new boolean[1000001];
prime[1] = false;
for(int k = 2; k <= MAX_VALUE; k++) {
prime[k] = true;
}
int i = 2;
while(i*i <= MAX_VALUE) {
for(int j = i+i; j <= MAX_VALUE; j = j + i) {
prime[j] = false;
}
i = i + 1;
}
for(int k = start; k <= end; k++) {
if(prime[k] == true) {
System.out.println(k);
}
}
sc.close();
}
}