에라토스테네스의 체

이름은 거창하지만 단순히 소수를 구하는 알고리즘이다.
구현 방법은 간단하다.

• 1. 소수를 검사하려는 범위 N을 설정한 뒤 크기가 N + 1인 배열을 선언하고
     배열의 값을 각각의 인덱스 값으로 채운다 ( 1은 소수가 아니므로 2부터 )

     int A[] = new int[N+1];
     
     for (int i = 2; i <= N; i++) {
     	A[i] = i;
     }

• 2. 2중 For문을 통해 i의 값이 소수일 경우 A[i]의 값을 0으로 초기화

        for (int i = 2; i <= Math.sqrt(N); i++) { // 제곱근까지만 수행하기
             if (A[i] == 0) {
                 continue;
             }
             // 배수 지우기
             for (int j = i + i; j <= N; j = j + i) {
                 A[j] = 0;
             }
         }

     Math.sqrt(N), 즉 N의 제곱근 까지만 탐색하는 이유 -

     N이 A * B 라고 가정했을 때, A와 B 모두 N의 제곱근 보다 클 수 없다.
     따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다.
     만약 16의 범위까지 소수를 구할 때 16 = 4 * 4 로 이뤄지면
     16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 된다는 뜻.
     따라서 4 까지만 확인하고 소수 판별을 진행하면 된다.
     

• 3. A[i] != 0 , 즉 소수가 아닌 값을 표기

     for (int i = 2 ; i <= N i++) {
     	if (A[i] != 0) {
         	System.out.print(A[i] + " ");
         }
     }
     

-  Java Code

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int A[] = new int[N + 1];

        // 크기가 N + 1 인 배열을 선언한 후 값은 각각의 인덱스값으로 채운다.
        // 1은 소수가 아니므로 2부터.
        for (int i = 2; i <= N; i++) {
            A[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(N); i++) { // 제곱근까지만 수행하기

            // 배수 지우기
            for (int j = i + i; j <= N; j = j + i) {
                A[j] = 0;
            }

        }

        for (int i = M; i <= N; i++) {
            if (A[i] != 0) {
                sb.append(A[i]).append("\n");
            }
        }

        System.out.println(sb);