一、质数判定（试除法）

1. 质数定义

大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数（素数）；否则称为合数。 核心注意：1既不是质数，也不是合数。

2. 暴力解法（O(n)，不推荐）

从2遍历到n-1，逐个判断是否有数能整除n。 缺点：当n很大时（如1e9），运行时间极长，完全无法使用。

3. 优化解法：根号优化（O(√n)）

优化原理

因数具有对称性：若 a × b = c，则两个因数中必然有一个 ≤ √c，另一个 ≥ √c。 因此只需遍历到 √n，就能判断n是否存在除1和自身外的因数，时间复杂度从O(n)大幅降至O(√n)。

代码实现

// 功能：判断x是否为质数
// 返回值：1表示是质数，0表示不是质数
bool isP(int x) {
    if(x <= 1) return 0;  // 小于等于1的数都不是质数
    for(int i = 2; i * i <= x; i++) { // 仅遍历到根号x
        if(x % i == 0) { // 存在其他因数，判定为合数
            return 0;
        }
    }
    return 1; // 遍历完无其他因数，判定为质数
}

易错提醒

• 边界处理：必须特判 x <= 1 的情况，直接返回非质数。
• 数据溢出：当x接近整型上限时，i*i 可能超出数据范围导致溢出出错，建议将变量定义为 long long 类型。

多组查询调用示例

signed main() {
    long long t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        if(isP(n)) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

---

二、因数总和计算

核心思路

同样利用因数的对称性，遍历到 √x：

• 若 i 是x的因数，则 x/i 也一定是x的因数
• 当 i == x/i 时（完全平方数），只累加一次，避免重复计算

代码实现

// 功能：计算x的所有因数的总和
int sum(int x) {
    int ans = 0;
    for(int i = 1; i * i <= x; i++) {
        if(x % i == 0) {
            if(i == x / i) ans += i;        // 完全平方数，因数重复，只加一次
            else ans += i + x / i;          // 加上一对因数
        }
    }
    return ans;
}

复杂度

时间复杂度：O(√x)

易错提醒

必须加 i == x/i 的判断，否则完全平方数的因数会被重复累加，结果偏大。

---

三、质因数个数统计

1. 算术基本定理（质因数分解定理）

任何一个大于1的自然数，都可以唯一分解成有限个质数的乘积，形式为：

$$n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}$$

其中 p₁ < p₂ < ... < p_k 是质数，a₁, a₂... 是对应质数的指数。

2. 统计思路

从小到大枚举因数i，用while循环把x中所有的i因子除尽，同时统计个数； 循环结束后，若剩余的x > 1，说明剩下的x本身是一个质数，需要额外计数。

代码实现

// 功能：统计x的质因数总个数（重复的质因数也计数）
// 示例：12=2*2*3，返回结果为3
int sum2(int x) {
    int ans = 0;
    for(int i = 2; i * i <= x; i++) {
        while(x % i == 0) { // 除尽x中所有的i因子
            ans++;
            x /= i;
        }
    }
    if(x > 1) ans++; // 剩余的数本身是质数，计入总数
    return ans;
}

示例理解

• 例1：x=12
  1. i=2：12%2=0 → ans=1，x=6；6%2=0 → ans=2，x=3
  2. i=3：i*i=9 > 3，循环结束
  3. x=3 > 1 → ans=3，最终结果为3
• 例2：x=9
  1. i=2：不整除，跳过
  2. i=3：9%3=0 → ans=1，x=3；3%3=0 → ans=2，x=1
  3. 循环结束，x=1不满足>1，最终结果为2

易错提醒

• 内层是while循环，不是if，必须把当前因数除干净。
• 末尾必须判断x>1，否则会漏掉最后一个大质因数。

---

四、埃氏筛法（埃拉托斯特尼筛法）

1. 应用场景

批量筛选 1~n 范围内的所有质数。当需要多次查询质数、且数据范围较大时，比逐个使用试除法效率高得多。

2. 核心思想

质数的所有倍数（除自身外）一定是合数。 从小到大遍历每个数，如果当前数未被标记（是质数），就把它的所有倍数标记为合数。

3. 代码实现

const int N = 1e6 + 10;
bool isP[N]; // 标记数组：isP[i]=0 表示i是质数，isP[i]=1 表示i是合数

int main() {
    int n;
    cin >> n;
    isP[0] = 1;
    isP[1] = 1; // 0和1都不是质数，提前标记
    
    for(int i = 2; i <= n; i++) {
        if(isP[i] == 0) { // 如果i是质数
            // 标记i的所有倍数为合数
            for(int j = i * 2; j <= n; j += i) {
                isP[j] = 1;
            }
        }
    }
    return 0;
}

4. 复杂度

时间复杂度：O(n log log n)，接近线性，n≤1e7时都能较快处理。

5. 进阶优化

标记倍数时，可以从 i*i 开始，而不是 i*2。 原因：小于i*i的倍数，已经被更小的质数标记过了（例如i=5时，10、15、20已经被2、3标记）。

// 优化后的内层循环
for(int j = i * i; j <= n; j += i) {
    isP[j] = 1;
}

易错提醒

• 数组大小要提前开够，建议比数据范围多预留几位（如+10），避免越界。
• 必须初始化0和1为合数状态。
• 筛法是预处理操作，预处理完成后，查询任意数是否为质数只需O(1)。

---

五、平方因子数筛选（埃筛思想延伸）

1. 定义

平方因子数：存在整数 k>1，使得 k² 能整除该数，即这个数包含完全平方数作为因数。 例如：4=2²、8=2³、12=2²×3 都是有平方因子的数；6、7、10 没有平方因子。

2. 核心思路

沿用埃筛的“倍数标记”思想：枚举所有平方数 k²，把它们的所有倍数都标记为“有平方因子”。

3. 代码实现

const int N = 1e6 + 10;
int is[N]; // is[i]=1 表示i有平方因子，默认0表示无平方因子

int main() {
    // 预处理：标记所有有平方因子的数
    for(int i = 2; i <= 1000; i++) { // 1000²=1e6，刚好覆盖1e6范围
        int pf = i * i; // 当前平方数
        for(int j = pf; j <= 1e6; j += pf) {
            is[j] = 1;
        }
    }
    
    // 示例：统计区间[n,m]中有平方因子的数的个数
    int n, m, ans = 0;
    cin >> n >> m;
    for(int i = n; i <= m; i++) {
        ans += is[i];
    }
    cout << ans;
    return 0;
}

易错提醒

• 枚举i的上限是 √max_n，比如数据范围到1e6，i枚举到1000即可，无需更大。
• 数组默认初始化为0，代表“无平方因子”，标记为1代表“有平方因子”。

---

六、方法对比与适用场景

方法	适用场景	时间复杂度	核心特点
试除法判质数	单次/少量查询、单个大数判断	O(√n)	代码简单，无需预处理
埃氏筛法	批量查询、范围固定的质数判定	预处理O(n log log n)，查询O(1)	一次预处理，多次快速查询
平方因子筛选	批量标记具有某类特征的数	预处理O(n/k)	埃筛思想的通用延伸，可解决多种倍数标记问题

---

七、高频易错点汇总

1. 1的特殊性：1既不是质数也不是合数，所有质数判定都要特判x≤1的情况。
2. 数据溢出：试除法中 i*i 容易溢出int范围，大数场景建议使用long long类型。
3. 完全平方数重复：因数求和、因数计数时，注意完全平方数的重复计算问题。
4. 质因数分解收尾：分解完成后必须判断剩余x是否>1，避免漏掉最后一个质数。
5. 筛法数组越界：开数组时要比数据范围多一点（如+10），防止循环时越界访问。