总结

质数，合数，因数，公因子，质因数，互质

1.质数：除了1和其本身为其因数，无其他因数的数
2.合数：除了1和其本身为其因数，还有其他因数的数
3.因数：能被某个数整除的数
4.公因子：两个数之间共同的因数
5.质因数：满足质数和合数的性质
6.互质：公因子只有1的两个数有的关系

相关关系：
1.合数/质数（任何数）总能被分解为质数的乘积
2.若 a 与 b 互质，则 a^n 与 b^m也互质（n,m 为正整数）
3.每个合数都可以唯一分解为质数的乘积（不考虑顺序）
4.GCD（最小公因数）:gcd(a,b) = gcd(b, a % b)
GCD(a,b)×LCM(a,b)=a×b
5.LCM（最大公倍数）:

埃式筛法

思想：根据当前的质数，筛选无论质数合数

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

线性筛法

思想：根据当前的最小质因子来筛选

代码：
for(int i = 2; i <= n; i)
{
if(!st[i])
{
primes[cnt ] = i;
for(int j = 0;primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}

}

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

//二维差分

public class Main
{
    static final int N = 1000010;
    static boolean[] st = new boolean[N];
    static int[] primes = new int[N];

    public static void main(String args[]) throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter log = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int cnt = 0;
        int n = Integer.parseInt(in.readLine());

        for(int i = 2; i <= n; i++)
        {
            if(!st[i])
            {
                primes[cnt ++] = i;
                for(int j = i; j <= n; j += i) st[j] = true;//此时，使用质数筛选数字
            }
        }
        log.print(cnt);

        log.flush();
    }
}

关于线性筛法的注释，为何是线性的证明：

for(int i = 2; i<= n; i++)
        {
            if(!st[i])primes[cnt++] = i;
            for(int j = 0;primes[j] <= n / i; j++)
            {
                st[primes[j] * i] = true;//此处的primes[i] * i 一定是由最小质因子来筛选的
                if(i % primes[j] == 0) break;//后续不再是最小质因子了
                // i % primes[j] == 0 : primes[j]从小到大遍历，第一次为i所整模，prime[j]一定是i的最小值质因子，
                // 因此也一定是primes[j] * i的最小质因子
                // i % primes[j] != 0 : primes[j]不被i整模,其最大公因子为1，故而primes[j] 与 i 互质，所以
                // 两个质数的乘积保证了 primes[j] * i一定是第一次被排除
                //因此，整个过程都只被处理一次，因而是线性的
            }
        }