16. 소수

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

 

 

입력 답

import java.util.Scanner;

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

        for(int i=2; i<=n; i++){
            if(arr[i] == 0){
                cnt++;
                for(int j=i; j<=n; j = j+i){
                    arr[j] = 1;
                }
            }
        }
        System.out.println(cnt);
    }
}

 

풀이 방법

* 소수 : 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미

* 다중 배열을 이용해 푸는 방법도 있지만, 그 경우 입력값이 큰 경우에는 시간 초과가 나기 때문에  " 에라토스테네스 체" 방법을 이용하여 구현해야 한다.

• 먼저 입력 값을 받은 뒤, 입력값 크기 만큼의 int 배열을 선언한다. 
• 배열의 초기값은 모두 0 인 상태이다.
• 그 후 2 부터 시작해, 2는 배열값이 0이므로 cnt ++ 후, 2 의 배수들을 모두 1로 수정한다. (배수는 자기 자신만을 약수로 가지지 않으므로 소수가 아니다!)
• 이 과정을 계속 반복한다.