- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
public class Eratostenes
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
if (num <= 1) return;
boolean[] arr = new boolean[num + 1]; //true 이면 해당 인덱스 소수.
arr[0] = arr[1] = false;
for (int i = 2; i <= num; i += 1) {
arr[i] = true;
}
//2 부터 숫자를 키워가며 배수들을 제외(false 할당)
for (int i = 2; i * i <= num; i += 1) {
for (int j = i * i; j <= num; j += i) {
arr[j] = false; //2를 제외한 2의 배수 false
}
}
System.out.println("Prime number list from 2 to " + num + " : ");
for (int i = 0; i <= num; i += 1) {
if (true == arr[i]) {
System.out.print(i + " ");
}
}
System.out.println();
}
}