[JAVA] 소수(에라토스테네스 체)

1. 문제

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

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

 

- 입력

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

 

- 출력

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

 

Ex)

- 입력

20

- 출력

8

 

2. 방법

- ar[]를 만든다. 모두 0으로 초기화 한다.

  소수 인지 판별해야 하기때문에 0,1은 필요 없고 2~20까지의 배열 값을 비교해 보자.

 

i	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
ar[i]	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

- 배열 ar[i]의 값이 0일때 결과 값을 위해 answer을 +1 하고 i의 값과 i의 배수의 값을 모두 1로 변경한다. 2가 0이므로 2의 배수 모두 1로 값을 변경한다.

i	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
ar[i]	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

- 3도 0이므로 answer에 +1 한 후 3의 배수를 모두 1로 값을 변경한다.

i	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
ar[i]	1	1	1	0	1	0	1	1	1	0	1	0	1	1	1	0	1	0	1

- 4의 값은 1이므로 패스 하고 5는 0이므로 answer값을 +1하고  5의 배수의 값을 1으로 변경한다.

i	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
ar[i]	1	1	1	1	1	0	1	0	1	0	1	0	1	1	1	0	1	0	1

- 계속 반복하면서 ar[i]가 0이면 결과값 answer에 +1하고 i의 배수들을 모두 1로 변경한다.

3. 코드

public class Ex_r5 {
    public int solution(int n) {
        int answer = 0; 
        int[] array = new int[n + 1]; 
        // 배열은 0부터 시작하기 때문에 20까지 배교하려면 n+1로 만들어야 한다.

        for (int i = 2; i <= n; i++) { //끝에 20까지 비교해야 하기때문에 n도 꼭 포함해야 한다.
            if (array[i] == 0) { //값이 0이라면
                answer++; //소수가 맞으니 결과값에 +1해준다.
                for (int j = i; j <= n; j = j + i) { //i의 배수 값을 반복한다
                    array[j] = 1; //i의 배수값을 모두 1로 변경해준다.
                }
            }

        }
        return answer;
    }