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

소수는  1보다 큰 정수 1과 자기 자신으로만 나누어지는 수로

영어로는 Prime Number 이다. 여기서 말하는 나누기란 자연수로 나누었을 때 나머지가 0인 경우를 의미한다.

 

ex)

    '1'은 '1보다 큰 정수'가 아니므로 소수가 아니다.
    '2'는 '1보다 큰 정수'이고 '1과 2 이외의 자연수로 나눌 수 없으므로 소수이다.

    '3'은 '1보다 큰 정수'이고 '1과 3 이외의 자연수로 나눌 수 없으므로 소수이다.
    '4'는 '1보다 큰 정수'이지만 '1과 4 이외에도 2로 나누는 것이 가능하므로 소수가 아니다.
    '5'는 '1보다 큰 정수'이고 1과 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 int solution(int n){
        int answer = 0;
        
        //동적 배열 할당 0~20까지 index가 필요하기 때문에 n + 1개 해주어야한다.
        int[] ch = new int[n+1];
        
        // 0 과 1은 소수가 아니기 때문에 index 2번 부터 시작 해서 20까지
        for(int i = 2; i <= 20; ++i){
        
            //동적할당 한 배열 인덱스의 각각 원소에는 0이 들어가있다.
            if(ch[i] == 0){
                ++answer;
                //if문이 참이면 현재 i의 배수들을 1로 만들어줌. 
                for(int j = i; j <= 20; j+=i){
                    ch[i] = 1;
                }
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Main pro = new Main();
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt(); //20 입력
        
        System.out.println(pro.solution(n)); //8이 출력됨
    }
}