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

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    public int solution(int n) {
        int answer = 0;
        int[] ch = new int[n+1];

        //* 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;
            }
        }
        //i가 2일 때 j가 2씩 증가 -> 2의 배수들을 1로 변환
        //i가 3일 때 j가 3씩 증가 -> 3의 배수들을 1로 변환
        //i가 4일 때 ch[4] == 1 이므로 넘어감

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();

        System.out.println(T.solution(n));


    }
}