에라스토테네스의 체

소수구할때 사용한다. 실행시간 줄이기 좋은 방법.

그림을 보면 알다시피 배열을 미리 선언후, 각 배수에 해당하는 칸을 칠해가면서 소수인지 아닌지 구분하는 방법이다.

https://www.acmicpc.net/problem/1929

자바 구현 소스

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        boolean[] isPrime = new boolean[1000001]; // 미리 배열 생성
        Arrays.fill(isPrime, true);

        isPrime[1] = false; // 1은 소수가 아니므로 제외
        for (int i = 2; i < isPrime.length; i++) {
            for (int j = 2 * i; j < isPrime.length; j += i) {
                isPrime[j] = false;
            }
        } 
        // 처음나오는 수 말고 그 이후의 배수는 전부 false로 변경

        for (int i = m; i <= n; i++) {
            if (isPrime[i]) System.out.println(i);
        }

    }
}