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

설명

소수의 개수를 구하라. N(2<=N<=200,000)

예시 입력 1 

20

예시 출력 1

8

 

<힌트>

에라토스테네스의 체를 통해서 구한다.

앞에서 부터 체크하는 방식으로 하면된다.

소수는 1과 자기자신 이외의 수로는 나눠지지 않는 수이다.

 

<정답코드>

import java.util.*;

public class Main {

    public static void main(String[] args) {

        //소수 구하기 ( 에라토스테네스의 체 )

        Scanner sc = new Scanner(System.in);

        int s = sc.nextInt();

        int answer = 0;

        int prime[] = new int[s+1];

        for( int i = 2; i < prime.length ; i++){

            if(prime[i] == 0){

                answer++;

                for( int j = i ; j < prime.length; j = j+i){

                    prime[j] = 1;

                }

            }

        }

        System.out.println(answer);

        sc.close();

    }

}