소수 구하기(에라토스테네스의 체)

자연수 N이 주어졌을때, 1부터 N 까지의 소수의 개수를 구하는 알고리즘

import java.util.Arrays;
import java.util.Scanner;
import java.io.IOException;

public class Main {
	/*
	 * 백준 문제 1929번
	 */
	public static void main(String[] args) throws IOException{
		
		Scanner scanner = new Scanner(System.in);
		int X, Y;
		X = scanner.nextInt();
		Y = scanner.nextInt();
        // 0, 1, 2, ... , Y
		boolean[] b = new boolean[Y+1];
    	// Default는 모두 소수라 가정
		Arrays.fill(b,Boolean.FALSE);
  	    // 1은 무조건 합성수
		b[1] = true;
        // 2부터 시작
		for (int i = 2; i < Y+1; i++) {
			// 소수의 배수들은 모두 합성수
            if(!b[i]){
				for(int j = i*2; j < Y+1; j = j + i){
					b[j] = true;
				}
			}
		}
		for(int i = X; i < Y+1; i++){
			if(!b[i]) System.out.println(i);
		}
	}
 }

원리는 소수의 배수는 모두 합성수이므로 소수 배수를 모두 걸러내어 소수를 구함