一、概念

Eratosthenes筛选法【埃拉托斯特尼筛法】（如果3是素数，那么6,9,12···一定不是素数 ）、欧拉筛法、拉宾-米勒 (R a b i n − M i l l e r Rabin-MillerRabin−Miller) 大数

二、模板

统计所有小于等于非负整数 n ( 0 ≤ n ≤ 5 × 106 ) 的素数的数量。

int countPrimes(int n){
          
   
	    int cnt = 0;   // 出现过素数的次数                           
	    int[] f = new int[5000001]; // 0=素数，1=合数
	    f[0] = f[1] = 1;  // 0 和 1 都不是素数，所以都标记为 1；                      
	    for(int i = 2; i <= n; ++i) {
          
   
	        if(f[i] == 0) {
          
   
	            ++ cnt;                             
	            for(int j = i * i; j <= n; j += i) {
          
     
	                f[j] = 1;                    
	            }
	        }
	    }
	    return cnt;
	}

三、例题

题：1175. 质数排列

请你帮忙给从1 到n的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。

让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。

示例 1：

输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。

示例 2：

输入：n = 100
输出：682289015

提示：

1 <= n <= 100

解：

解题思路：Eratosthenes筛选法

AC代码：

class Solution {
          
   
    public int numPrimeArrangements(int n) {
          
   
        int[] f = new int[101];
        int cnt = 0;
        f[0] = f[1] = 1; // 0是素数，1是合数
        for(int i = 2; i <= n; i ++) {
          
   
            if(f[i] == 0) {
          
    // 如果是素数
                cnt ++;
                for(int j = i * i; j <= n; j += i){
          
   
                    f[j] = 1;
                }
            }
        }
        long ans = 1L;
        // cnt个质数排列组合
        ans = pai(ans, cnt);
        // n-cnt个合数排列组合
        ans = pai(ans, n - cnt);
        return (int)ans;
    }
    // 求x个排列组合
    long pai(long ans, int num) {
          
   
        for(int i = 2; i <= num; i ++)
            ans = (ans * i) % (long)(1e9 + 7);
        return ans;
    }
}

题：剑指 Offer 49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1 是丑数。
n 不超过1690。

解：

解题思路：动态规划

AC代码：

class Solution {
          
   
    public int nthUglyNumber(int n) {
          
   
       int a = 0, b = 0, c = 0; // 三指针 
       int[] dp = new int[n]; // 存储第几个丑数
       dp[0] = 1;
       for(int i = 1; i < n; i ++) {
          
   
           dp[i] = Math.min(dp[a] * 2, Math.min(dp[b] * 3, dp[c] * 5));
           // 判断a，b，c的贡献
           if(dp[a] * 2 == dp[i]) a ++;
           if(dp[b] * 3 == dp[i]) b ++;
           if(dp[c] * 5 == dp[i]) c ++;
       }
       return dp[n - 1]; 
    }
}