题目描述

算法1 朴素做法O(nlogn)或埃氏筛O(nloglogn)

import java.util.*;
public class Main{
    static int N = 1000010,cnt;
    static int[] pr=  new int[N];
    static boolean[] st = new boolean[N];
    //朴素法(所有数的倍数都删掉)
    public static void find(int n){
        for(int i = 2 ; i <= n ; i ++ ){
            if(!st[i]) pr[cnt++] = i;
            for(int j = i+i ; j <= n ; j += i ){
                st[j] = true;
            }
        }
    }
    //埃氏筛(所有质数的倍数删掉)
    public static void find(int n){
        for(int i = 2 ; i <= n ; i ++ ){
            if(!st[i]){
                pr[cnt++] = i;
                for(int j = i+i ; j <= n ; j += i ){
                    st[j] = true;
                }  
            } 
        }
    }
    public static void  main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        find(n);
        System.out.println(cnt);
    }
}

线性筛（欧拉筛）O(n)

import java.util.*;
public class Main{
    static int N = 1000010,n,cnt;
    static int[] pr = new int[N];
    static boolean[] st= new boolean[N];
    public static void find(int n){
        for(int i = 2 ; i <= n ; i ++ ){
            if(!st[i]) pr[cnt++] = i;//将没有被标记的点加入到pr数组中去，也就是质数
            for(int j = 0 ; pr[j] <= n / i; j++){//从小到大遍历质数
                st[pr[j]*i] = true; //每一次让pr[j]*i标记
                if(i % pr[j] == 0) break;
                //只要i % pr[j] == 0说明他是pr[j]*i的最小质因数了,然后结束循环，
                //如果不break循环的话就会进行pr[j+1]*i晒掉，因为pr[j+1]*i的最小质因数
                //不是pr[j+1],所以会导致重复删除，这也是线性筛的优点所在
                //例如：st[2*4=8]标记之后，如果你不在下面判断if(4%2==0)break掉
                //就会继续pr[(j+1)]*i== st[3*4=12],3不是12的最小质因数，所以这样也是
                //会导致重复删除，执行到i=6时候，st[2*6=12]会再次标记，这样也就在此导致重复了

                //i % pr[j] != 0 说明pr[j]永远是pr[j]*i的最小质因数
                //因为pr[j]的最小质因数是本身pr[j]，然后pr[j]*i是pr[j]的倍数
                //所以pr[j]*i的最小质因数也是pr[j]，永远都是，pr[j+1]*i的时候也是
            }
        }
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n  = scan.nextInt();
            find(n);
            System.out.println(cnt);
    }
}