[Java] 1929 소수 구하기

문제

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

        입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

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

 

요약하자만 입력하는 M부터 N까지의 숫자 사이의 소수를 구하는 문제이다.

 

소수를 구하는 여러 방법이 있겠지만 에라토스테네스의 체를 활용해서 풀어보겠다.

 

에라토스테네스의 체?

수학에서 에라토스테네스의 체는 소수를 찾는 빠르고 쉬운 방법.

1. 2부터N까지모든수를써놓는다.

2. 아직지워지지않은수중에서가장작은수를찾는다.

3. 그수는소수이다.

4. 이제그수의배수를모두지운다.

5. 찾는 수의 배수가 N보다 커질 때까지 반복한다. 남은 수가 소수다.

문제 풀이

1. 구하려는 범위 내의 가장 큰 수인 N에  1을 더한 값 N+1 크기의 boolean 배열을 생성한다.

1.1 boolean 배열의 Default Value는 false, 차후 로직 상 True로 변경한 인덱스들을 소수가 아닌 값의 위치로 취급한다.

1.2 배열의 범위가 N + 1인 이유는 범위가 1 ~ 100까지라고 했을 때 배열의 인덱스는 0부터 시작하는데 숫자는 1부터 시작하기 때문에 인덱스 위치가 1씩 비틀린다. 그렇기 때문에 + 1을 해주어 위치 값을 조절할 수 있도록 한다.

2. 계산된 소수들을 저장할 int 배열을 생성한다.

3. 2부터 N까지의 for문을 실행한다. (for문의 int 값을 i로 명명한다.)

4. 만약 boolean 배열의 i 인덱스 위치가 false일 경 아직 검사되지 않은 값(혹은 소수)로 취급한다.

5. false인 인덱스 i 값 중 M보다 크거나 같은 값만 구해야한다.

5.1 M보다 크거나 같은 값일 경우 해당 인덱스 i 값을 int 배열에 담는다.

5.2 이후 N보다 작은 i의 배수들의 boolean 배열 값을 true로 변경한다.

5.3 M보다 작은 i의 경우 int배열에 담지는 않고 배수들의 값을 true로 변경하는 작업만 진행한다.

6. 이후 int안에 들어있는 숫자들을 출력한다.

 

자바 코드

import java.util.Scanner;

public class GetPrimeNumber {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int primeCount = 0;
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();

        boolean[] numbersCheck = new boolean[num2 + 1];
        int[] primeNumber = new int[num2 - num1 + 1];
        for(int i = 2; i <= num2; i++){
            if(!numbersCheck[i]) {
                if (i >= num1) {
                    primeNumber[primeCount++] = i;
                }
                for (int j = i * 2; j <= num2; j += i){
                    numbersCheck[j] = true;
                }
            }
        }

        for(int i : primeNumber) {
            if(i == 0)
                break;

            System.out.println(i);
        }

        sc.close();
    }
}