[BAEKJOON] 1929번

import java.util.Scanner;
 
public class Main {
    private final static int SIZE = 1000000;
    
    public static void main(String[] args) {
        run();
    }
    
    public static void run() {
        boolean[] isComp = new boolean[SIZE];
        int i, j;
        Scanner sc = new Scanner(System.in);
 
        isComp[0] = isComp[1] = true;
        for (i = 2; i < SIZE; ++i)
        {
            if (!isComp[i])
            {
                for (j = i << 1; j < SIZE; j += i)
                {
                    isComp[j] = true;
                }
            }
        }
 
        i = sc.nextInt();
        j = sc.nextInt();
 
        for (; i <= j; ++i)
        {
            if (!isComp[i])
            {
                System.out.println(i);
            }
        }    
        
        sc.close();
    }
 
}

C에서는 배열 길이가 길면 실행이 안 된다.

에라토스테네스의 체(Eratosthenes`s sieve) 알고리즘의 기본적인 형태다.

배열의 이름을 isPrime 이 아닌 isComp로 하고 소수인 경우 false를 저장한 것은 Java에서 boolean형 배열의 모든 요소는 자동으로 false로 초기화되므로 불필요한 반복을 없앨 수 있기 때문이다.