素数判断

  • 素数判断

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

  • 代码实现

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

// 素数判断
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(); // 记录开始时间

    // 素数判断
    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 ~ 106 中有多少个质数，我们可以使用一种筛选的思路，如下
    2、一个合数，一定存在非 1 非本身的质因子，比如 4 = 2 * 2，其中2 为质因子。如果把 2 的倍数全部筛掉(标记为合数)，便可以筛除 2, 4, 6, …
    3、这样，我们只需要判断到sqrt(N)有哪些质数，比sqrt(N)大的部分会被质因子倍数筛掉，这种朴素筛法的效率有所提高(106 - 159ms, 107 - 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就是埃氏筛。欧拉筛比朴素筛法效率又有所提高(107 - 1635ms)，时间复杂度达到 O(n*loglogn)

    #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, ...}，这便是遍历中将得到的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、欧拉线性筛的一大优势是它将质数记录在了数组中(且升序排列)；另一优势是效率更快(107 - 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;
}

页底评论