1-3筛质数

算法思想

朴素筛法

1. 从小到大遍历（从2开始）
2. 使用质数筛去和数
   1. 找到第一个质数 p，然后筛去 p 的所有倍数
3. 继续筛选，直到 sqrt(n)
4. 注意事项
   1. 同一个和数可能会被筛选多次
      1. 例如，6分别被2和3各筛选了一次

线性筛法

1. 从小到大遍历
2. 使用最小质因数筛去和数
3. 继续筛选，直到遍历结束

算法模板

朴素筛法

import java.util.Scanner;

public class Main {
    static int N = 1000010;
    static int cnt,
        n;
    static int[] primes = new int[N];
    // st[i]标记 i 是否为质数；true 表示不是质数
    static boolean[] st = new boolean[N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        getPrimes(n);
        System.out.println(cnt);
    }
    
    public static void getPrimes(int x)
    {
        for(int i = 2; i <= x; i ++ )
        {
            if(!st[i])
            {
                primes[cnt ++] = i;
				// 使用质数筛去和数
                for(int j = i + i; j <= n; j += i)
                    st[j] = true;
            }
        }
    }
}

线性筛法

import java.util.Scanner;

public class Main {
    static int N = 1000010;
    static int cnt,
        n;
    // primes[]存储小于等于 n 的所有质数，所有质数顺序排列
    static int[] primes = new int[N];
    // st[i]标识 i 是否为质数；true 表示不是质数
    static boolean[] st = new boolean[N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        getPrimes(n);
        
        System.out.println(cnt);
    }
    
    public static void getPrimes(int x)
    {
        for(int i = 2; i <= x; i ++ )
        {
            if(!st[i]) primes[cnt ++] = i;
            
            for(int j = 0; primes[j] <= n / i; j ++ )
            {
                int k = primes[j] * i;
                st[k] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }
}

参考资料

1. 【数学】线性筛质数 (欧拉筛)_哔哩哔哩_bilibili