题目描述
给定一个正整数 n，请你求出 1∼n中质数的个数。
输入格式

共一行，包含整数 n。
输出格式

共一行，包含一个整数，表示 1∼n

中质数的个数。
数据范围

1≤n≤10^6

输入样例：

8

输出样例：

4

import java.util.Scanner;

public class Main{
    static final int N = 1000010;
    static int[] primes = new int[N];//如果要打印具体的，就输出这个数组
    static boolean[] st = new boolean[N]; 
    static  int cnt=0;

    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        int n = sc.nextInt();
        get_Primes(n);
        System.out.println(cnt);
    }
    static void get_Primes(int n){
        for(int i=2;i<=n;i++){

            //第一次进入for循环时i=2，为质数cnt++，等于1
            if(!st[i]){
                primes[cnt] = i;
                cnt++;
            }

            //j+i+i每次for循环将i翻倍；将1~n的整数翻倍，并在对应位置赋值true，进行标记

            for(int j=i+i;j<=n;j+=i){//此for循环进行了n/i次
                st[j] = true;
            }
        }
    }
}