基础知识

• 定义1：整数p除了1和本身之外，没有其他的约数，那么p就被称为质数（或素数）。反之被称为合数
• 定义2：若a是合数，则必有质数p，使得p整除a（p|a）。合数a的最小非显然约数（除了a和1本身的约数）一定是素数。
• 定义3：一个整数的因数如果是素数，则这个因数称为该整数的质因数。
• 定义4：设整数a>=2 ，若a是合数，则必有质数p，使得p整除a(p|a)，p\leq\sqrt{a}

埃式筛选法

题目背景

输入正整数 N，求 1 \sim N 范围内质数的个数，其中 2 \le N \le 10000000。

算法分析

根据埃氏筛选法的思想，首先在 f 数组里从 f[2] ~ f[N] 依次存放 2 \sim N 的所有自然数。 从 i=2 开始，只要 f[i] 不为 0（此时 f[i] 的值就是 i），就将 f[i] 的倍数（f[i] 本身除外）删除，实现时只需将 f 数组里对应元素的值置为 0(false) 即可。 根据定义4，N 以内的合数 a，必有质数 i，满足 i \le \sqrt{N} 且 i|a，所以 i 循环到 \sqrt{N} 即可。 最后，f 数组里非零的元素就是保留下来的质数，把这些质数保存到新的数组里，变量 num 记录统计到的质数的个数。

埃氏筛选法要求 i 为质数，但在实现时，无需判断 f[i]（其值就是循环变量 i）是否为质数，因为如果 f[i] 为合数，根据定义3，它一定有小于它本身的质因数，从而 f[i] 在之前就已经被置为 0 了。 代码如下。

#include<bits/stdc++.h>
using namespace std;
int n, m;
bool f[10000005];
void primes(int n)
{
    memset(f, true, sizeof f);//初始默认全部都是素数
    f[0] = f[1] = false;
    for (int i = 2; i*i <= n; i++) 
        if (f[i])
            for (int j = i; i*j <= n; j++) 
                f[i*j] = false;
}
int main()
{
    cin >> n >> m;
    primes(n);
    while(m--)
    {
        int x;
        cin >> x;
        if (f[x])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

注意：在上述实现方法中，对给定的质数p，依次删除p的2倍、3倍、…，直至超过N。而在筛选法的改进——线性筛法中，是对给定的自然数i，依次删除f[0]的i倍、f[1]的i倍、…。 上面的代码从质数p出发，删除p的倍数（保留p本身），可能将同一个合数删除多次，例如n=30，当p=2,3,5时，都会将30删除一次，当n很大时，就会很浪费时间。

埃式筛的改进-线性筛选

基本思想：确保每个合数只被它的最小质因数删除一次。

实现方法如下。使用全局数组 na（初始自动置为 0），na[i] = 0 表示 i 为质数，na[i] = 1 表示 i 不是质数。用 pri 数组存储已找到的质数。从 i=2 开始遍历每个自然数 i，如果 na[i] 为 0，则 i 为质数，马上把 i 存入 pri 数组中。然后对当前的自然数 i，乘以当前质数表中前面一些质数 pri[j]，pri[j] * i 一定是合数，把 na[pri[j] * i] 置为 1，即删除合数 pri[j] * i。对每个自然数 i，“提前结束当前删除合数的工作”的条件为：i % pri[j] == 0。这是因为，由于是从小到大枚举质数pri[j]，则pri[j]是pri[j] * i的最小质因数；当i % pri[j] == 0时，即i是pri[j]的倍数，假设i = pri[j] * t，终止当前删除合数的工作；如果不终止，那么接下来要被删除的合数依次是pri[j + 1], pri[j + 2], …与i相乘得到的合数，但这些合数的最小质因数不是pri[j + 1], pri[j + 2], …，以pri[j + 1] * i为例，pri[j + 1] * i = pri[j + 1] * pri[j] * t，它的最小质因数至少也应该是pri[j]；如果不停止删除合数工作，就会使得一个合数被删除多次。

例如，当i = 2时，判断出2是质数，存入pri数组，此时pri数组已存入了1个质数，就是2，然后删除2 * 2 = 4，即将na[2 * 2]置为1。接着因为i % pri[j]为0，结束当前删除合数的工作。继续，当i = 3时，判断出3是质数，存入pri数组，此时pri数组已存入了两个质数，就是2和3，然后删除2 * 3 = 6、3 * 3 = 9。接着因为i % pri[j]为0，结束当前删除合数的工作。

总结

本讲的核心在于解决“如何高效找出范围内所有素数”的问题。随着数据规模的增大（如 10^7 或 10^8），简单的试除法会超时，必须使用空间换时间的筛选法。

埃拉托斯特尼筛法 (Sieve of Eratosthenes)

2. 原理：从2开始，将每个素数的倍数（2倍及以上）标记为合数。

3. 缺点：一个合数可能被其多个质因子重复标记（例如12会被2和3分别标记一次）。

4. 时间复杂度：O(N log log N)

5. 线性筛 / 欧拉筛 (Euler Sieve)

6. 原理：核心优化是“每个合数只被其最小质因子筛掉”。

7. 优点：完美解决了重复筛选的问题，确保每个合数仅被访问一次。

8. 时间复杂度：O(N)，即线性时间。

经典题目解析

数组技术与筛法_筛法求质数

思路解析：

1. 如果使用暴力判断，那么时间会超时（O(n*\sqrt(n))）
2. 可以预先将所有的质数筛选出来保存在数组里面查询即可。

暴力判断，不能拿满分

#include<bits/stdc++.h>
using namespace std;
bool isprime(int x)
{
    if(x < 2) return false;
    for(int i = 2; i*i <= x; i++)
        if(x%i == 0)
            return false;
    return true;
}
int n, m;
int main()
{
    cin >> n >> m;
    while(m--)
    {
        int x;
        cin >> x;
        if(isprime(x))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

优化之后

#include<bits/stdc++.h>
using namespace std;
int n, m;
bool f[10000005];
void primes(int n)
{
    memset(f, true, sizeof f);
    f[0] = f[1] = false;
    for (int i = 2; i*i <= n; i++) 
        if (f[i])
            for (int j = i; i*j <= n; j++) 
                f[i*j] = false;
}
int main()
{
    cin >> n >> m;
    primes(n);
    while(m--)
    {
        int x;
        cin >> x;
        if (f[x])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

B-smooth数

1. 将所有数的最大质因子求出来保存，依次判断即可
2. 在求质因数的时候，我们是正序筛选的。所以新值会覆盖旧值。保留下来的就是最大质因数

#include <bits/stdc++.h>
using namespace std;

int n, b, cnt, f[10000005];

void primes(int n)
{
    f[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!f[i])
        {
            f[i] = i;
            for (int j = 2; i*j <= n; j++) 
            {
                f[i*j] = i;
            }
        }
    }
}


int main() 
{
    cin >> n >> b;
    primes(n);
    for(int i = 1; i <= n; i++)
        if(f[i] <= b)
            cnt++;
    cout << cnt;
    return 0;
}

亲和数

1. 将每个数的真因数求出来之后累加保存起来即可，接下来判断两个数是否相等即可

#include<bits/stdc++.h>
using namespace std;

int m, f[2000005];

int main()
{
    cin >> m;
    for (int i = 1; i <= m; i++)
        for (int j = 2; i*j <= m; j++)
            f[i*j] += i;
    int sum = 0;
    for (int i = 1; i < m; i++)
    {
        int j = f[i];
        if (i < j && j < m && f[j] == i) //先判断大小防止越界
            sum += i + j;
    }
    cout << sum;
    return 0;
}

线性筛素数

#include<bits/stdc++.h>
using namespace std;


int n, q, cnt, p[10000005];
bool f[100000005];
void EulerSieve(int n)
{
    memset(f, true, sizeof(f));
    for(int i = 2; i <= n; i++)//要筛选的数组
    {
        if(f[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt && i*p[j] <= n; j++)//查询素数表
        {
            f[i * p[j]] = 0;
            if(i%p[j] == 0) break;
        }
    }
}
int main()
{
    cin >> n >> q;
    EulerSieve(n);
    while(q--)
    {
        int k;
        cin >> k;
        cout << p[k] << "\n";
    }
    return 0;
}