$$\color{Red}{筛质数:从埃氏筛法到线性筛法}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

朴素筛法：
假设求1-n内的所有质数，把2->n-1中每个数的2 -> ...(最大筛到乘积为n)的倍数筛除，即所有的合数的2及以上的倍数筛除。

埃氏筛法：
从2开始每当筛选到一个数，如果它是质数，那就把这个质数小于n的2以上的倍数锁定，缺点是如果类似12，势必会被3，4都重复锁定，数越大效率越高

void is_prime(int n)
{
    for(int i=2; i<=n; i++)
    {
        if(!st[i])

        {
            prime[cnt++] = i;
            for(int j=i; j<=n; j+=i) st[j] = true;
        }    
    }
}

java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n, N = 1000010, cnt;
    static boolean[] st = new boolean[N];
    static int[] prime = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void is_prime(int x) {
        for (int i = 2; i <= n; i++) {
            if (!st[i]){
                prime[cnt++] = i;
                for (int j = i; j <= n; j+=i) st[j] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        is_prime(n);
        System.out.println(cnt);
    }
}

线性筛法：
怎样才能避免重复筛选呢？
如果我们每次筛到一个质数，只需要把小于它的最小质因子的数与它相乘的数锁定，那么就是唯一的锁定方式了。
那么为什么可以这样？
我们可以把我们每次筛到的数字i当成一个倍数，然后用j每次从小到大遍历目前已经筛到的质数，若i % primes[j] != 0，因为质数是从小到大遍历，不满足这个，说明pj目前小于i的最小质因子。那么pj * i的最小质因子显然根据算数基本定理，应该是pj。
若i % primes[j] == 0，说明此时pj是i的最小质因子，所以i能被拆分成pj乘以它别的质因数的形式,那么pj * i的最小质因子显然应该也是pj。

我们每次就按这个点，找到每个数的最小质因子pj然后再把它乘i的倍数筛除，保证能只筛倒它一次（最小质因子只有一个）。

然后在pj刚好为i的最小质因子的时候break（再大pj可能就不是pj * i的最小质因子了。

void is_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])  primes[cnt++] = i;
        //遍历n内部的最小质数
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            //此时pj为pj * i的最小质因子，筛除它i倍数的数
            st[primes[j] * i] = true;
            //此时pj为i的最小质因子，再大下去没有意义，后续更大的因子i会遍历乘到它
            if(i % primes[j] == 0) break;
        }
    }
}

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n, N = 1000010, cnt;
    static boolean[] st = new boolean[N];
    static int[] primes = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void getPrime(int x) {
        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;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        getPrime(n);
        System.out.println(cnt);
    }
}