质数和质因数

质数是指只能被1和自身整除的正整数。

  • 质数排列：请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。
  • 204. 计数质数：给定整数 n ，返回 所有小于非负整数 n 的质数的数量。
  • 2523. 范围内最接近的两个质数
    这些题目都可以用一些常见的算法来解决，例如素性测试、埃氏筛、欧拉筛等。

因数用于描述两个正整数的整除关系。当 除数 a 被 被除数 b 整除且模为 0 时，a 是 b 的因数。

质因数是指能整除一个数的质数1。在力扣上，有一些题目是关于质因数的，例如：

  • 丑数：丑数 就是只包含质因数 2、3 和 5 的正整数。给你一个整数 n ，请你判断 n 是否为 丑数。
    功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5）。
  • 丑数 II：给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。
  • 2521. 数组乘积中的不同质因数数目
  • 2507. 使用质因数之和替换后可以取到的最小值
    这些题目都可以用一些常见的算法来解决，例如分解质因式、动态规划等。

求质数的算法：线性筛和欧拉筛

线性筛和欧拉筛是两种用于求质数的算法，它们的核心思想是让每个合数只被它的最小质因数筛去，从而达到线性时间复杂度。

方法一：埃氏筛

  • 思路：
    • 若 i 是质数，筛掉 i 的倍数；如果没有被小于自己的数筛掉，就是质数
    • 从 i * i 开始筛，更小的已经被i之前的质数筛掉了
  • 时间复杂度
    • 预处理：每个质数 i，循环 MX/ i 次, O(loglogMX)
    • MX范围内的质数个数：MX / logMX
    • 二分时间复杂度：O(log(MX / logMX))
    • 枚举范围内的数组：O(r / log r - l / log l)

方法二：线性筛（欧拉筛）

  • 思路：
    • 每个合数只被划掉一次
    • 被它的最小质因子划掉
  • 时间复杂度：O(MX)

代码

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void linearSieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    int[] primes = new int[n + 1];
    int cnt = 0;
    Arrays.fill(isPrime, true);
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void eulerSieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    int[] phi = new int[n + 1];
    int[] primes = new int[n + 1];
    int cnt = 0;
    Arrays.fill(isPrime, true);
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            } else {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

C++ 版本
参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 埃式筛
class Solution {
public:
    vector<int> closestPrimes(int left, int right) {        
        vector<int> res(2, -1);

        // 埃式筛
        vector<bool> isPrimes(right + 1, true);  // 从 [1, right] 的数都是质数
        vector<int> primes;  // 质数

        for (int i = 2; i <= right; ++i) {
            // 1. 不是质数
            if (!isPrimes[i]) continue;
            // 2. 是质数
            if (i >= left) primes.emplace_back(i);
            // 将质数的倍数都设置为 false
            for (int j = 2; j <= (right + 1) / i; ++j) {
                isPrimes[i * j] = false;
            }
        }

        if (primes.size() < 2) return res;
        res[0] = primes[0];
        res[1] = primes[1];
        for (int i = 2; i < primes.size(); ++i) {
            if (res[1] - res[0] > primes[i] - primes[i - 1]) {
                res[0] = primes[i - 1];
                res[1] = primes[i];
            }
        }

        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 线性筛
class Solution {
public:
    vector<int> closestPrimes(int left, int right) {        
        vector<int> res(2, -1);

        // 线性筛
        vector<bool> isPrimes(right + 1, true);  // 从 [1, right] 的数都是质数
        vector<int> primes;  // 质数

        for (int i = 2; i <= right; ++i) {
            // 是质数
            if (isPrimes[i]) primes.emplace_back(i);
            // 标记该数与最小质因数的乘积为非素数
            for (int p: primes) {
                // 两个素数的乘积已经超过 right 了
                if (p > right / i) break;
                isPrimes[p * i] = false;
                // 找到第一个最小质因子就撤
                if ((i % p) == 0) break;
            }
        }

        // 二分法找到第一个 ≥ left 的质数
        if (primes.size() < 2 || primes[primes.size() - 2] < left) return res;
        int firstIdx = lower_bound(primes.begin(), primes.end(), left) - primes.begin();        
        res[0] = primes[firstIdx]; 
        res[1] = primes[firstIdx + 1];
        for (int i = firstIdx + 2; i < primes.size(); ++i) {
            if (res[1] - res[0] > primes[i] - primes[i - 1]) {
                res[0] = primes[i - 1];
                res[1] = primes[i];
            }
        }

        return res;
    }
};

【质数】例题

2523. 范围内最接近的两个质数

分享🤏笔记（来自灵神的视频讲解哦）

  1. 第一步：预处理找到范围内所有的质数（有两种方法：埃氏筛、线性筛）
  2. 第二步：用二分法找到第一个 ≥ left 的质数
  3. 第三步：找符合条件（质数差最小）的 两个质数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findValidSplit(int[] nums) {
    int n = nums.length;
    Map<Integer, Integer> left = new HashMap<Integer, Integer>(); // left[p] 表示质数 p 首次出现的下标
    int[] right = new int[n]; // right[i] 表示左端点为 i 的区间的右端点的最大值

    for (int i = 0; i < n; i++) {
        int x = nums[i];
        // d 表示从
        for (int d = 2; d * d <= x; ++d)  // 分解质因数
            if (x % d == 0) {
                // 遇到质因数           
                // ...
                for (x /= d; x % d == 0; x /= d) ;
            }
        if (x > 1)
            if (left.containsKey(x))
                right[left.get(x)] = i;
            else
                left.put(x, i);
    }
}
    1. 分割数组使乘积互质

【因数】例题

2427. 公因子的数目

找出两个正整数的公因子的数目。