质数相关算法课堂笔记

一、质数的定义与判断

1.1 质数的定义

质数（Prime Number）又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

• 最小的质数是2（唯一的偶数质数）
• 1既不是质数也不是合数

1.2 判断一个数是否为质数（isPrime函数）

函数功能

判断一个整数x是否为质数，是则返回1（真），否则返回0（假）

代码实现

bool isPrime(int x) {
    if(x <= 1) return 0;  // 小于等于1的数不是质数
    for(int i = 2; i * i <= x; i++) {  // 循环检查因数
        if(x % i == 0) return 0;  // 若能被整除，则不是质数
    }
    return 1;  // 是质数
}

关键思路解析

1. 边界处理：直接排除x≤1的情况
2. 优化的循环范围：只需检查到i×i≤x
   • 原理：如果x有一个大于√x的因数，那么它必定有一个小于√x的对应因数
   • 例如：15的因数有3和5，√15≈3.87，3<3.87，5>3.87
3. 判断逻辑：若存在能整除x的数，则x不是质数

二、计算数字的最大质因数（jisuan函数）

2.1 质因数的定义

质因数是指能整除给定正整数的质数，最大质因数即其中最大的那个。

函数功能

计算并返回整数x的最大质因数

代码实现

int jisuan(int x) {
    int i = 2;
    while(i * i <= x) {  // 循环查找质因数
        while(x % i == 0) {  // 若i是x的因数
            x /= i;  // 除以所有的i因数
        }
        i++;  // 检查下一个可能的因数
    }
    if(x > 1) return x;  // 剩余的x是最大质因数
    return i - 1;  // 否则返回最后一个质因数
}

关键思路解析

1. 分解过程：从最小的质数2开始，不断去除x中包含的该质因数
2. 循环结束条件：当i×i>x时停止
3. 结果判断：
   • 若剩余的x>1，则x本身就是最大质因数（例如x=28，最后剩余7）
   • 否则返回最后一个有效质因数

示例说明

以x=12为例：

• i=2时，12能被2整除，12÷2=6，6÷2=3，此时x=3
• i递增到3，3×3>3，循环结束
• 剩余x=3>1，返回3（12的最大质因数是3）

三、质数筛选算法

3.1 两种主要筛选算法对比

3.2 欧拉筛法（Euler's Sieve）

算法功能

高效筛选出一定范围内（≤N）的所有质数

核心思想

• 把遇到的质数存储在质数数组中
• 对于每个数字i，将其与已发现的质数相乘，标记乘积为合数
• 关键优化：每个合数只被它的最小质因数筛一次

代码实现

int p[N/10], cnt;  // p数组存储质数，cnt统计质数个数
bool isP[N];       // 标记数组：isP[i]==0表示i是质数，isP[i]==1表示i是合数

signed main() {
    isP[1] = 1;  // 1不是质数
    for(int i = 2; i <= N-10; i++) {
        if(isP[i] == 0)  // 若i是质数
            p[++cnt] = i;  // 将i加入质数数组
        
        // 遍历当前已发现的质数
        for(int j = 1; j <= cnt && i * p[j] <= N-10; j++) {
            isP[i * p[j]] = 1;  // 标记i*p[j]为合数
            
            // 关键判断：若p[j]是i的质因数，则停止循环
            if(i % p[j] == 0) 
                break;
        }
    } 
    return 0;
}

关键代码解析

1. 初始化：isP[1] = 1，明确标记1不是质数
2. 外层循环：遍历从2到N的所有数字
   • 若当前数字i是质数（isP[i] == 0），则加入质数数组p
3. 内层循环：用已发现的质数标记合数
   • i * p[j]：表示要标记的合数
   • i % p[j] == 0：当p[j]是i的质因数时，说明p[j]是i*p[j]的最小质因数，此时停止循环，确保每个合数只被最小质因数标记一次

为什么效率高？

• 每个合数只会被它的最小质因数标记一次
• 避免了埃氏筛中一个合数被多个质因数重复标记的问题
• 时间复杂度达到线性O(n)，适合处理大规模数据

四、总结与应用场景

1. isPrime函数：适用于单个数字的质数判断，时间复杂度O(√x)
2. jisuan函数：适用于求解数字的最大质因数，常用于数论问题
3. 欧拉筛法：适用于需要生成大量质数的场景（如密码学、数论研究），尤其是当N很大时，优势明显

通过这些算法，我们可以高效处理与质数相关的各种问题，从单个数字的判断到大规模质数的筛选，形成了完整的质数操作工具集。