위 문제는 백준 사이트의 알고리즘 1929 문제에 관한 설명입니다.

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        int i, j;
        boolean Array[] = new boolean[N + 1];
        for (i = 0; i <= N; i++)
        	Array[i] = true;
        Array[1] = false;

        for (i = 2; i <= N; i++)
            for (j = 2; i * j <= N; j++)
                Array[i * j] = false;

        for (i = M; i <= N; i++)
        	if (Array[i] == true) System.out.println(i);
        scanner.close();
    }
}

제가 푼 소스코드입니다.

코드 설명

이번 문제는 저번 포스팅처럼 풀었다가는 시간초과가 나오게 됩니다.

그 이유는 입력값의 범위(1 ≤ M ≤ N ≤ 1,000,000)때문 입니다.

만약 2부터 for문을 시작해서 1,000,000번 돌아간다면? 당연히 오래걸릴 수 밖에 없습니다.

그래서 “에라토스테네스의 체” 개념을 이용한 방법을 사용합니다.

1.2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

2.2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

3.자기 자신을 제외한 2의 배수를 모두 지운다.

4.남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

5.자기 자신을 제외한 3의 배수를 모두 지운다.

6.남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

7.자기 자신을 제외한 5의 배수를 모두 지운다.

8.남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

9.자기 자신을 제외한 7의 배수를 모두 지운다.

10.위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

이 부분을

   for (i = 2; i <= N; i++)
     for (j = 2; i * j <= N; j++)
         Array[i * j] = false;

이와 같이 표현했습니다.

소수구하기