埃氏筛, 时间复杂度$O(n*lnln(n))$

import java.util.*;
import java.io.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int N = 1000_005;
    public static int cnt = 0;      // cnt记录质数的个数
    public static int[] primes = new int[N]; 
    public static int[] minp = new int[N];   //minp[i]: 存i的最小质因数
    public static boolean[] st = new boolean[N];

    //埃氏筛
    public static void init_aishi(int n){
        Arrays.fill(minp, Integer.MAX_VALUE);

        for(int i =  2; i <= n; ++i){
            if(!st[i]){
                primes[cnt ++] = i;
                minp[i] = i;
                for(int j = i + i; j <= n; j += i){
                    st[j] = true;
                    if(minp[j] > i) minp[j] = i;
                }
            }
        }
    }
}

线性筛，时间复杂度: $O(n)$

import java.util.*;
import java.io.*;

public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int N = (1 << 20) + 10;
    public static int cnt = 0;      // cnt记录质数的个数
    public static int[] primes = new int[N]; 
    public static int[] minp = new int[N];   //minp[i]: 存i的最小质因数
    public static boolean[] st = new boolean[N];

    // 线性筛
    public static void init(int n){
        for(int i = 2; i <= n; ++i){
            if(!st[i]) {
                primes[cnt ++] = i;
                minp[i] = i;
            }
            for(int j = 0; j < cnt && i * primes[j] <= n; ++j){
                st[i * primes[j]] = true;
                minp[i * primes[j]] = primes[j];

                if(i % primes[j] == 0) break;
                // i % primes[j] == 0
                // 换言之，i 之前被 primes[j] 筛过了
                // 由于 primes 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
                // primes[j] 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
                // 掉就好了
            }
        }
    }
}