배열.에라토스테네스 체(소수 구하기)

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

📌 소수 구하는 것 중에 제일 빠른 것 = 에라토스테네스 체

📌 N이 200,000니까 이중for문 돌리면 시간제한 걸리니 무조건 에라토스테네스 체로!!

설명

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

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

입력

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

출력

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

예시 입력 1

20

예시 출력 1

8

📌에라토스테네스 체

📌int[] ch … n+1개 갖는 체크배열 만들기

📌기본값 0에서 소수인 애들은 1로 바꿔주면서 answer++;

import java.lang.reflect.Array;
import java.util.*;
import java.util.Scanner;

class Main {
    public int solution(int n) {
        //체크배열 만들기. n+1개만큼 만들어야 인덱스번호가 n까지 생김
        //0하고 1은 소수의 대상아니니까 2부터 보기
        int[] ch = new int[n + 1];
        int answer = 0;
        //2부터 n까지 돌기 n+1까지 해놨으니 이하로 해도 상관없음
        //n이 20이면 2,3,4,5,6,7,8,9,10..20
        for (int i = 2; i <= n; i++) {

            if (ch[i] == 0) {
                answer++;
                //조심 j= j+i -> i배수를 찾아서 1로 체크해놓는 거니까!
                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 sc = new Scanner(System.in);
            int n = sc.nextInt();
            System.out.println(T.solution(n));

        }
    }