백준 1929번(에라토스테네스의 체) 자바 풀이

문제

내 풀이

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 0, 1 번째 인덱스를 제외한 나머지를 true로 세팅
		boolean[] sosu = new boolean[1000000];
		sosu[0] = false;
		sosu[1] = false;
		for(int i = 2; i < sosu.length; i++) {
			sosu[i] = true;
		}
		// 에라토스테네스의 체를 이용하여 소수가 아닌 인덱스를 false로 변경
		for(int i = 2; i < sosu.length; i++) {
			if(sosu[i]) {
				for(int j = 2*i; j < sosu.length; j += i) {
					sosu[j] = false;
				}
			}
		}
		
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		// a에서 b 사이의 true(소수)인 인덱스 값을 출력
		for(int i = a; i <= b; i++) {
			if(sosu[i]) {
				System.out.println(i);
			}
		}
		sc.close();
	}	
}

에라토스테네스의 체 알고리즘

• 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열
2. 2는 소수
3. 자기 자신을 제외한 2의 배수를 모두 지움
4. 남아있는 수 가운데 3은 소수
5. 자기 자신을 제외한 3의 배수를 모두 지움
6. 남아있는 수 가운데 5는 소수
7. 자기 자신을 제외한 5의 배수를 모두 지움
8. 남아있는 수 가운데 7은 소수
9. 자기 자신을 제외한 7의 배수를 모두 지움
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.