素数判断


  • 素数判断

    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 < 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 ~ 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;
    }

页底评论