质数筛 | 山暮云秋

素数判断

素数判断

1、最简单的判断质数的方式，便是从 $2 \to x$ 依次尝试，如果尝试到有因子，则其不是质数。需要特判 $2$ 为质数、小于 $2$ 的都不是质数(质数范围是大于 $1$ 的自然数)
2、朴素筛法可以简单进行优化，实际需要尝试的因子最多只到 $\sqrt{x}$ 。比如判断 $25$ 时，易知只需要判断 $2 \to 5$ 有没有因子，因此不需要重复判断 $\gt \sqrt{x}$ 的因子。提前使用变量记录 $\sqrt{x}$ ，可以避免循环中重复计算sqrt的开销
3、但假如要计算 $2 \to 10^6$ 中有多少个质数时，只使用素数判断的效率很低($10^6$ - $218ms$)，其额外判断了大量无用的数据，所以需要效率更高的筛法

代码实现

#include <ctime>
#include <iostream>
using namespace std;

// 素数判断
bool is_prime(int x)
{
    // 特判
    if (x < 2)
        return false;
    if (x == 2)
        return true;

    // 用 x / i 表示 sqrt(x)，不要写 i * i <= x，容易越界
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int N = 1e6, ct = 0; // 记录质数个数

    double s = clock(); // 记录开始时间

    // 素数判断
    for (int i = 2; i <= N; i++)
        if (is_prime(i))
            ++ct;

    double e = clock(); // 记录结束时间

    cout << ct << endl << e - s << "ms";
    return 0;
}

朴素筛法

朴素筛法

1、假如要计算 $2 \to 10^6$ 中有多少个质数，我们可以使用一种筛选的思路，如下
2、一个合数，一定存在非 $1$ 非本身的质因子，比如 $4 = 2 \times 2$ ，其中 $2$ 为质因子。如果把 $2$ 的倍数全部筛掉(标记为合数)，便可以筛除 $2, 4, 6, \ldots$
3、这样，我们只需要判断到 $\sqrt{n}$ 有哪些质数，比 $\sqrt{n}$ 大的部分会被质因子倍数筛掉，这种朴素筛法的效率有所提高($10^6$ - $159ms$, $10^7$ - $2482ms$)

代码实现

#include <ctime>
#include <iostream>
using namespace std;

const int maxn = 1e6 + 10;
bool exclude[maxn]; // false 表示是素数，true 表示是合数，默认全部为 false

// 素数判断
bool is_prime(int x)
{
    // 特判
    if (x <= 1)
        return false;
    if (x == 2)
        return true;

    // 用 x / i 表示 sqrt(x)，不要写 i * i <= x，容易越界
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int N = 1e6, ct = 0; // 记录质数个数

    double s = clock(); // 记录开始时间

    // 朴素筛法，这种筛选只需要到 sqrt(N)
    for (int i = 2; i <= N / i; i++)
    {
        if (is_prime(i))
        {
            // 将该质数的所有倍数(除本身)都标记为合数
            for (int j = 2 * i; j <= N; j += i)
                exclude[j] = true;
        }
    }
    // 统计质数
    for (int i = 2; i <= N; i++)
    {
        if (!exclude[i])
            ct++;
    }

    double e = clock(); // 记录结束时间

    cout << ct << endl << e - s << "ms";
    return 0;
}

埃氏筛法

埃氏筛法

1、上面朴素筛法实际上不需要is_prime函数，直接从 $exclude[i]$ 中获取是否是质数即可。因为循环筛选的过程中，例如 $2, 3, 4, 5, 6$ 的倍数都没有筛去 $7$，那么 $7$ 一定是质数
2、在此基础上，将标记倍数的循环变量 $j$ 的初值从 $j = 2 * i$ 变为 $j = i * i$ 就是埃氏筛。欧拉筛比朴素筛法效率又有所提高($10^7$ - $1635ms$)，时间复杂度达到 $O(n \log \log n)$

#include <ctime>
#include <iostream>
using namespace std;

const int maxn = 1e6 + 10;
bool exclude[maxn]; // false 表示是素数，true 表示是合数，默认全部为 false

// 修改：删除了 is_prime 函数

int main()
{
    int N = 1e6, ct = 0; // 记录质数个数

    double s = clock(); // 记录开始时间

    // 埃氏筛法，这种筛选只需要到 sqrt(N)
    for (int i = 2; i <= N / i; i++)
    {
        // 修改：可以直接从 not_prime[i] 获取是否是质数
        if (!exclude[i])
        {
            // 将该质数的所有倍数(除本身)都标记为合数
            // 修改：j = 2 * i 改为 j = i * i
            for (int j = i * i; j <= N; j += i)
                exclude[j] = true;
        }
    }
    // 统计质数
    for (int i = 2; i <= N; i++)
    {
        if (!exclude[i])
            ct++;
    }

    double e = clock(); // 记录结束时间

    cout << ct << endl << e - s << "ms";
    return 0;
}

欧拉线性筛

欧拉线性筛

1、埃氏筛的筛选过程中，同一个合数会被多个质因子重复筛去，比如 $120$ 会重复被 $2$、$3$、$5$ 筛去。欧拉筛便可以优化这一问题
2、从小到大枚举每个数，如果当前数没被划掉则记录当前数为质数。层内再枚举已记录的质数 $prime[j]$ ，划去最小质因子为 $prime[j]$ 的合数($prime[j]$ 的 $i$ 倍)。i % prime[j] == 0则中断，可以保证每个合数只被最小质因子划去；因为若 $i$ 是质数，则最多枚举到自身中断；若 $i$ 是合数，则最多枚举到自身的最小质因子中断
3、例如，$prime$ 数组中应为 $\{2, 3, 5, 7, \ldots\}$，这便是遍历中将得到的 $prime[j]$ 的值。例如此刻 $i$ 为 $25$，则 $prime[j] * i$ 将得到 $\{50 = 2 * 25, 75 = 3 * 25, 125 = 5 * 25\}$ ，它们都是最小质因子为 $prime[j]$ 的合数，且该合数一定首次被划去；但继续向下 $175 = 7 * 25 = 7 * 5 * 5$ 时，最小质因子为 5，表示该合数一定在某次最小质因子为 $5$ 时被划去过，此后的合数同理，因此此时便应该中断循环
4、欧拉线性筛的一大优势是它将质数记录在了数组中(且升序排列)；另一优势是效率更快($10^7$ - $1601ms$)，时间复杂度为 $O(n)$

#include <ctime>
#include <iostream>
using namespace std;

const int maxn = 1e7 + 10;
bool exclude[maxn];         // false 表示是素数，true 表示是合数，默认全部为 false
int prime[maxn], pp;        // prime 保存素数，pp 记录下标

int main()
{
    int N = 1e7, ct = 0;  // 记录质数个数

    double s = clock();   // 记录开始时间

    // 欧拉线性筛，从 2 遍历到 N
    for (int i = 2; i <= N; i++)
    {
        // 如果 i 是素数，则 prime 记录 i
        if (!exclude[i])
            prime[pp++] = i, ct++;

        // prime[j] * i 即最小质因子为 prime[j] 的合数，i 为倍数
        for (int j = 0; prime[j] * i <= N; j++)
        {
            // 标记 prime[j] * i 是合数
            exclude[prime[j] * i] = true;
            // 保证 prime[j] 是合数 prime[j] * i 的最小质因子
            if (i % prime[j] == 0)
                break;
        }
    }

    // 修改：删除统计质数的循环，因为可以合并到上一循环中

    double e = clock(); // 记录结束时间

    cout << ct << endl << e - s << "ms";
    return 0;
}

素数判断

朴素筛法

埃氏筛法

欧拉线性筛

页底评论