[Java | Algorithm] 소수의 개수를 출력하시오. (에라토스테네스 체)

소수 갯수를 구하는 관련 문제는 굉장히 많이 접해왔는데(ㅡ.ㅡ) 풀때마다 까먹는 것 같아서 이김에 확실히 정리해두고 넘어가려고 한다.

인프런에서 자바 알고리즘 코테대비 강의를 듣고있고 해당 문제는 강의의 내용을 참조하였다.

---

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

입력

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

출력

첫 줄에 소수의 개수를 출력합니다.

---

에라토스테네스 체

 

에라토스테네스는 소수를 구하는 방법중에서 가장 빠른 방법이다. 제곱근을 이용해 구하는 방법보다 빠른 방법 !

예제에서 n이 200,000까지 나올 수 있으므로 2중 for문으로 소수를 구하는 것은 시간제한이 걸려 실패한다.

 

n+1만큼의 배열을 할당하고 인덱스를 이용해 소수를 구하는 방법이다.

n+1만큼 할당하는 이유는 n번째 index를 이용해야 하기 때문이다.

 

해당 index 배열의 값이 0이라면 소수로 check하고 해당하는 index 값의 배수의 배열의 값을 증가시킨다.

따라서 소수가 아님을 표현할 수 있다. 배수라면 해당 index 값을 약수로 가지므로 소수가 아니게 되는 것을 이용하는 것이다.

 

예를 들어, index 값이 2라면 arr[2]는 0이므로 소수로 check한다. 이후 arr[4], arr[6], arr[8], arr[10] ... 은 2를 약수로 가지므로 소수가 아님을 판별할 수 있다. 

package inflearn.Array;

import java.util.Scanner;

public class Array5 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n+1];

        System.out.println(new Array5().solution(n, arr));
    }

    public int solution(int n, int[] arr){
        int answer = 0;

        for(int i=2; i<=n; i++){ // 0과 1은 소수가 아니므로 2부터 시작. index 번호를 n까지 사용해야 하므로 n을 포함하는 범위
            if(arr[i] == 0){
                answer++;
                for(int j=i; j<=n; j+=i){ // j는 i의 배수만큼 증가. 해당 배수는 i를 약수를 가지므로 소수가 아님이 판별된다.
                    arr[j] = 1;
                }
            }

        }

        return answer;
    }
}