mobile wallpaper 1
mobile wallpaper 2
mobile wallpaper 3
mobile wallpaper 4
Profile Image of the Author
Stella
近期公告
博客搬迁中wordpress --> astro
标签
1890 字
5 分钟
质数与筛法
2026-03-31
算法
质数
/
筛法

质数与筛法#

质数的判定——试除法#

质数：在大于 1 的整数中，如果只包含 1 和本身这两个约数，就被称为质数，或者叫素数。

判定方法： 试除法——从小到大枚举 2 ~ √n，只要有一个数能整除 n，n 就是合数；全部枚举完都没有，n 就是质数。

为什么只枚举到 √n？ 约数总是成对出现：若 d 是 n 的约数，则 n/d 也是，且这对约数中较小的那个一定 ≤ √n。所以只要 √n 以内没有约数，更大范围内也一定没有。

实现细节： 循环条件写 i <= n / i 而不是 i * i <= n，可以避免 i * i 溢出。时间复杂度 O(√n)。

import java.util.Scanner;


public class Main {
    // 试除法判定质数，O(sqrt(n))
    public static boolean isPrime(int n) {
        if (n < 2) return false;          // 1 既不是质数也不是合数
        for (int i = 2; i <= n / i; i++) { // 写成 i <= n / i 避免溢出
            if (n % i == 0) return false;
        }
        return true;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int x = sc.nextInt();
            System.out.println(isPrime(x) ? "Yes" : "No");
        }
    }
}

分解质因数——试除法#

（2）分解质因数——试除法 最坏O(sqrt（n）) ,实际在logn到sqrt(n)之间

方法： 从 2 到 √n 枚举 i，若 n 能被 i 整除，就把 i 除尽（记录指数），i 一定是质数——因为合数因子早被更小的质因子除掉了。循环结束后若 n > 1，说明剩下的 n 本身是一个大于 √n 的质因子（一个数最多只有一个大于 √n 的质因子），单独输出即可。

import java.util.Scanner;


public class PrimeFactorization {


    // 质因数分解：把 n 拆成质因子及其指数
    public static void divide(int n) {
        for (int i = 2; i <= n/i; i++) {
            if (n % i == 0) {          // 找到一个质因子
                int exp = 0;
                while (n % i == 0) {   // 除到不能再除
                    n /= i;
                    exp++;
                }
                System.out.println(i + " " + exp);
            }
        }
        if(n > 1) System.out.println(n + " " + 1);
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if (x > 1) divide(x);
        sc.close();
    }
}

质数筛-埃拉托斯特尼筛法（筛 1~n 的所有质数）#

埃拉托斯特尼筛法（简称“埃氏筛”）的核心原理一句话就能说清：

把每个质数的所有真倍数全部剔除，剩下的就是质数。

1️⃣ 为什么“剩下的”一定是质数？#

  • 初始假设：2~n 的所有数都是质数（st[] 全为 false）。
  • 从 2 开始，一旦发现一个数 还没被剔除，它不可能是任何更小数的倍数 ⇒ 它只能是质数。
  • 于是把它所有的倍数（≥2倍）全部标记为合数（st[j] = true）。
  • 往后扫描，重复这一过程，直到 √n 即可。

2️⃣ 为什么只需筛到 √n？#

  • 如果 n 有因子 > √n，那么对应的另一个因子必然 < √n。
  • 所以在剔除阶段，所有合数一定已经被其最小质因子剔除过了。
  • 代码里为了简洁直接写到 n，时间损失可忽略；严格优化可只写到 i*i <= n。

复杂度#

  • 时间：O(n log log n) （每个合数仅被其最小质因子剔除一次，调和级数求和得到 log log n 项）
  • 空间：O(n)（布尔数组）
import java.util.*;


public class SievePrimes {
    static final int N = 1_000_010;
    static int[] primes = new int[N]; // 存放质数
    static int cnt = 0;               // 质数个数
    static boolean[] st = new boolean[N]; // true 表示合数


    // 埃氏筛：把 2~n 的所有质数筛出来
    static void getPrimes(int n) {
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {            // i 是质数
                primes[cnt++] = i;
                for (int j = i + i; j <= n; j += i) {
                    st[j] = true;    // 标记合数
                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        getPrimes(n);
        // 输出质数个数
        System.out.println(cnt);
        // 可选：输出所有质数
        // for (int i = 0; i < cnt; i++) System.out.println(primes[i]);
        sc.close();
    }
}

线性筛法#

线性筛（欧拉筛）的核心思想只有一句话：

每个合数只被其「最小质因子」筛掉一次， 因此时间复杂度严格 O(n)。

为什么埃氏筛慢？#

埃氏筛里同一个合数可能被 多个质因子 重复标记。 例：

  • 30 会被 2 筛一次（2×15）
  • 又被 3 筛一次（3×10）
  • 还被 5 筛一次（5×6）

重复工作 → 多出的 log log n 因子。

线性筛的两大关键#

  1. 从小到大枚举质数 primes[]
  2. 对于当前质数 p，只筛「p × 某个合数」且该合数的最小质因子 ≥ p 一旦 i % p == 0 就 立即 break，保证以后只让 p 的更小倍 去筛，不会重复。
import java.util.*;


public class LinearSieve {
    static final int N = 10_000_010;       // 与原 C++ 一致
    static int[] primes = new int[N];      // 存储质数
    static int cnt = 0;                    // 质数个数
    static boolean[] st = new boolean[N];  // true 表示合数


    // 线性筛：2~n 的所有质数
    static void getPrimes(int n) {
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {                // i 是质数
                primes[cnt++] = i;
            }
            // 枚举已筛出的质数，筛掉合数
            for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;      // 只筛一次
                if (i % primes[j] == 0) break; // 保证最小质因子
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        getPrimes(n);
        System.out.println(cnt);   // 输出质数个数
        sc.close();
    }
}

试除法求约数个数#

试除法是一种直接且基础的算法，用于找出一个正整数的所有约数，并可以进一步计算其约数个数。

一、算法原理#

对于一个正整数 n，其约数总是成对出现。具体来说，如果 d 是 n 的一个约数，那么 d**n 也是 n 的一个约数。这一性质提示我们，只需检查从 1 到 n 的所有整数，即可找到 n 的所有约数。

步骤如下：

  1. 初始化一个计数器 count = 0。
  2. 遍历从 1 到 int(√n) 的每个整数 i。
  3. 对于每个 i，检查 n % i == 0：
    • 如果 i * i == n，说明 i 是 n 的平方根，计数器加 1（因为 i 和 n/i 是同一个数）。
    • 如果 i * i < n，说明 i 和 n/i 是两个不同的约数，计数器加 2。
  4. 最终，count 的值即为 n 的约数个数。

✅ 1. 试除法求一个数的所有约数#

含义： 使用试除法来找出一个正整数所有约数的方法。

方法： 从 1 开始，依次尝试每个数是否能整除给定的数 n，如果能整除，则这个数就是 n 的一个约数。

优化： 只需遍历到 n​，因为如果 i 是 n 的约数，那么 i**n​ 也一定是约数。

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


public class Main {
    /* 返回 n 的所有正约数，升序 */
    static List<Integer> getDivisors(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <= n / i; i++) {
            if (n % i == 0) {
                res.add(i);
                if (i != n / i) res.add(n / i);
            }
        }
        Collections.sort(res);
        return res;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        List<Integer> divs = getDivisors(n);
        /* 按题目要求输出：一行，空格分隔 */
        StringBuilder sb = new StringBuilder();
        for (int d : divs) sb.append(d).append(' ');
        System.out.println(sb.toString().trim());
    }
}

✅ 2. 约数个数#

含义： 求一个正整数有多少个正约数。

方法： 通常使用质因数分解法更高效，但试除法也可以做到：

  • 用试除法找出所有约数，然后统计个数；
  • 或者用质因数分解：
  • 若 n=p1e1⋅p2e2⋯pkekn = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}，
    则约数个数为：
    (e1+1)(e2+1)⋯(ek+1)(e_1 + 1)(e_2 + 1)\cdots(e_k + 1)

公式理解： 每个质因子 p_i 在约数中出现的次数可以是 0 ~ e_i，共 e_i + 1 种选择；各质因子的选择互相独立，乘法原理相乘即得总个数。

import java.util.*;


public class Main {
    static final int MOD = (int)1e9 + 7;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();


        // 统计所有质因子出现总次数
        Map<Integer, Integer> primes = new HashMap<>();


        while (n-- > 0) {
            int x = sc.nextInt();
            // 试除法分解质因数
            for (int i = 2; i <= x / i; i++) {
                while (x % i == 0) {
                    x /= i;
                    primes.merge(i, 1, Integer::sum); // 次数+1
                }
            }
            if (x > 1) primes.merge(x, 1, Integer::sum);
        }


        // 约数个数公式
        long res = 1;
        for (int cnt : primes.values()) {
            res = res * (cnt + 1) % MOD;
        }
        System.out.println(res);
    }
}

✅ 3. 约数之和#

含义： 求一个正整数的所有正约数的和。

方法： 同样可以用质因数分解：

若 n=p1e1⋅p2e2⋯pkekn = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}，
则约数之和为：
(1+p1+p12+⋯+p1e1)×⋯×(1+pk+pk2+⋯+pkek)(1 + p_1 + p_1^2 + \cdots + p_1^{e_1}) \times \cdots \times (1 + p_k + p_k^2 + \cdots + p_k^{e_k})

公式理解： 把每个括号展开，正好枚举了每个质因子的所有幂次组合，每一项对应一个约数。

import java.util.*;


public class Main {
    static final int MOD = (int)1e9 + 7;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> primes = new HashMap<>();


        while (n-- > 0) {
            int x = sc.nextInt();
            for (int i = 2; i <= x / i; i++)
                while (x % i == 0) {
                    x /= i;
                    primes.merge(i, 1, Integer::sum);
                }
            if (x > 1) primes.merge(x, 1, Integer::sum);
        }


        long res = 1;
        for (var entry : primes.entrySet()) {
            int p = entry.getKey();
            int a = entry.getValue();
            long t = 1;
            while (a-- > 0) t = (t * p + 1) % MOD;
            res = res * t % MOD;
        }
        System.out.println(res);
    }
}

总结一句话：

这张图讲的是如何找一个数的所有约数、约数有多少个、以及这些约数的总和是多少，主要基于试除法和质因数分解两种思路。

最大公约数-欧几里得算法#

一、数学原理：为什么 “gcd(a, b) = gcd(b, a mod b)” 恒成立？

  1. 公约数集合不变 设 d 是 a 和 b 的任意一个公约数，则 d | a 且 d | b ⇒ d | (a − kb) 对任意整数 k 成立。 取 k = ⌊a/b⌋，就有 a mod b = a − kb，因此 d | (a mod b)。 反之若 d | b 且 d | (a mod b)，同样可推出 d | a。 所以 {a, b} 与 {b, a mod b} 拥有完全相同的公约数集合，自然 最大公约数也相同。
  2. 终止条件 任何非负整数对在有限步 mod 后必出现 0： gcd(x, 0) = x，算法停止。

二、几何直觉：”矩形裁剪法“

想象一个 a × b 的长方形（a ≥ b）。 每次裁掉尽可能多的 b × b 正方形，剩下一块 b × (a mod b) 的小长方形。 重复裁剪，直到剩下 0 × g 的条，则 g 就是原始边长 a、b 的最大公约数。 这就是欧几里得算法的 几何版本。

一句话总结： 辗转相除——大数除以小数取余，把问题缩小为”小数与余数”的 gcd，直到余数为 0。每次取模至少让较大的数减半，因此复杂度为 O(log(max(a, b)))。

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


public class Main {
    static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringBuilder out = new StringBuilder();
        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            out.append(gcd(a, b)).append('\n');
        }
        System.out.print(out);
    }
}
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

质数与筛法
https://blogstella.xyz/posts/数据结构之质数与筛法/
作者
Stella
发布于
2026-03-31
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

组合计数
贪心算法
相关文章 智能推荐
1
欧拉函数与快速幂
算法 欧拉函数（单点与线性筛）、欧拉定理及其证明、快速幂、快速幂求逆元、扩展欧几里得算法的入门讲解与 Java 实现。
2
数位统计与状态压缩DP
算法 数位统计（按位枚举求数字出现次数）与状态压缩 DP（蒙德里安的梦想、最短 Hamilton 路径）的入门讲解与 Java 实现。
3
离散化与区间合并
算法 离散化（排序去重 + 二分映射）与区间合并的入门讲解与 Java 实现，处理值域巨大但实际用到的点很少的场景。
4
线性同余方程与中国剩余定理
算法 线性同余方程 ax ≡ b (mod m) 的求解与中国剩余定理（两两合并法）的入门讲解与 Java 实现。
5
树形DP与记忆化搜索
算法 树形 DP（没有上司的舞会）与记忆化搜索（最长滑雪轨迹）的入门讲解与 Java 实现。
随机文章 随机推荐
1
并查集
算法 2026-03-31
2
双指针算法与位运算
算法 2026-04-01
3
LangChain之05：Tools
LangChain 2026-08-14
4
Git使用详解
工具 2026-03-12
5
离散化与区间合并
算法 2026-03-31
© 2026 Stella. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录