[배열] 5. 소수(에라토스테네스 체)

5. 소수(에라토스테네스 체)

 

설명

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

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

입력

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

출력

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

예시 입력 1 

20

예시 출력 1

8

 

 

<<풀이>>

 

이 문제는 사실 노가다하면 바로 풀 수는 있지만 시간 복잡도가 N^2으로 엄청 커지고 느려지는 경향이 있다. 즉, 코딩테스트 채점시 시간초과로 점수가 깎인다. 

 

그래서 이 문제는 에라토스테네스 체 라는 방식을 이용한다.

 

즉 20까지의 수가 있다면 1을 제외하고 2부터해서 자기 자신을 제외하고 나누어 제거 시켜나가면서 최종적으로 제거 되지 않은 갯수가 소수 임을 이용하는 것이다.

 

이를 코드로 다루면

 

import java.util.Scanner;

class Main {
    public int soltuion(int n) {
        int answer = 0;
        int[] ch = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (ch[i] == 0) {
                answer++;
                for (int j = i; j <= n; j = j + i) ch[j] = 1;

            }
        }
        return answer;
    }


        public static void main (String[]args){
            Main T = new Main();
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            System.out.println(T.soltuion(n));
        }

}

 

 

2 부터 시작해서 2의 배수는 1로 바꾸고 3의 배수도 1로 바꾼다. 이때 4의 배수는 2의 배수가 이미 1로 만들어 놨기 때문에 필요가 없다.

그러면서, 0이 나올 때 answer 값을 증가시킨다.

 

이 문제의 흐름을 잘 파악하자.