素性测试

素性测试可以使用朴素法解决,朴素法的复杂度为O(n),一般情况下,单个素数的素性判定已经够用了,不过利用素数的性质,我们可以再将其复杂度从O(n)优化到O(\sqrt{n}),因为我们都知道一个数的约数是成对存在的(即6有约数2,那么6必有约数3)且\sqrt{n}*\sqrt{n}=n,那么这意味a*b=n不存在ab同时大于或者小于\sqrt{n}的情况,所以我们就只需要判断到\sqrt{n}即可,例如6,我们只需要从2枚举到\sqrt{6}即可,因为2*33*2实际上重复计算了,只不过需要注意的是在算法竞赛中,我们最好应该避免使用pow()sqrt(),尤其是当传入参数为整型时,所以我们这里使用i*i<=n而非i<\sqrt{n},另外需要注意边界条件,如果少了等号,那么就会出错。 ```c++ bool is_prime(int n)//朴素法判断质数O(sqrt(n)) { for(int i=2;i*i<=n;i++) { if(n%i==0)return false; } return n!=1;//1不是质数,最小的质数是2 }

#约数枚举
约数枚举和上面思路一样稍加变通即可
```c++
vector<int> enum_prime(int n)//朴素法枚举约数O(sqrt(n))
{
    vector<int>ys;
    for(int i=1;i*i<=n;i++)//易错点,枚举约数需要从1开始,而判断质数需要从2开始
    {
        if(n%i==0)
        {
            ys.push_back(i);
            if(i!=n/i)ys.push_back(n/i);
        }
    }
    return ys;
}

质因数分解

质因数分解这里用到的是短除法,也就是我们小学时学到的那种分解质因数的方法。大致思路是从最小的整数2开始,一直累除2,直到剩下的数不能被2整除,于是除下一个素数,也就是3,重复步骤,即可分解质因数,具体我们以代码说明 ```c++ //短除法分解质因数 //复杂度:O(sqrt(n)) map<int,int>prime_factor(int n)//map<int,int>存放质因数,map[i]=n i代表质数,n代表该质数的指数 { map<int,int>res; for(int i=2;i*i<=n;i ++) { while(n%i==0) { res[i]++;//map int型的初始值为0 n/=i; } } if(n!=1)res[n]=1; return res; }


#素数定理与埃氏筛法
如果只对一个整数进行素性测试,一般情况下$O(\sqrt{n})$的算法足以,但是如果要对一个大区间的数进行素性测试,那么就有点吃力了,对于这种问题,我们使用埃氏筛法(埃拉托斯特尼筛法)
埃氏筛法的主要思路是首先将2到n范围内所有的整数写下来,其中最小的数字2是素数,将表中所有的2的倍数划去,然后表中剩余的最小数字是3,它不能被更小的数整除,所以是素数,在讲表中所有的3的倍数都花去,以此类推,如果表中剩余的最小的数字是m时,m就是素数(因为m不是前面所有数的约数,不然早就被划掉了),然后将表中m的倍数都划去,由此反复聚能一次枚举n以内的素数。正如下图所示:
![](https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif)
假设有这样一个题,要求你求第n个素数,那么你该如何解决呢?很显然,埃氏筛法是个不错的选择。但是,于此同时另一个问题接踵而来,我该如何知道第i个素数大概在哪个区间里呢,如果无法求得我们只能通过估计一个很大的数来实现,但是很显然,很多情况下会造成空间浪费。
不过,使用素数定理可以解决这个问题。
素数定理可以简单的用以下等式表示:
![](https://zbit.io/usr/uploads/2019/09/2476963268.png)
其中$π(x)$表示小于或等于自然数$x$的所有素数个数,例如10,$\frac{10}{ln10}=4.3$,意味着10以内的质数大概有4个,不过需要注意的是2是个例外,$\frac{2}{ln2}=2.8$,但是2以内的质数只有2一个。在实现算法的时候需要特别小心特例。
代码如下:
```c++
//素数筛法模板-埃氏筛法-求第n个质数
// 复杂度:O(nloglogn)
// Created by zbit on 2019/9/27.
//测试用例:
//第100个质数是:541;
//第500个质数是:3571;
//第1000个质数是:7919;
//第10000个质数是:104729;
//第70000个质数是:882377。
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
vector<int> sieve(int n)
{

    vector<int>prime;//prime[i-1]代表第i个素数是多少
    vector<bool>is_prime;//is_prime[i]代表i是不是质数
    int max_n = 2;//估计需要创建至少多大的数组,需要从2开始,因为sqrt(1)==0,分母为0无意义
    if(n==2)max_n=3;
    else while (max_n / log(max_n) < n)max_n++;//根据素数定理估计使用埃氏筛法需要分配多少大小的数组
        //cout << "max_n:" << max_n << endl;//调试用语句,输入出应该分配的数组大小
    is_prime.assign(max_n + 1, true);//为判断某个数是不是素数的数组分配max_size个空间,初始化值为真
    is_prime[0] = is_prime[1] = false;//特殊情况,必须要保证最小的数是质数

    for (int i = 2; i < is_prime.size(); i++)//从2开始直到数组结束
    {
        if (is_prime[i])//判断最小的数是不是质数,不是则判断下一个最小的数
        {
            prime.push_back(i);//如果是则将其加入prime
            for (int j = 2 * i; j < is_prime.size(); j += i)
            {
                is_prime[j] = false;//并且将i的倍数全部标记为不是质数
            }
        }

    }
    //for (auto i : prime)cout << i << " ";//调试语句,用于输出得到的所有质数
    return prime;//返回素数数组
}
int main()
{
    int n;//n为第n个质数
    cin >> n;
    vector<int> prime=sieve(n);
    cout<<"\ntarget:"<<prime[n-1];//注意是N-1不是N;

    return 0;
}

举一反三,求n以内有多少个素数也同理,但是相对于求第n个质数要简单不少,代码如下: ```c++ //素数筛法模板-埃氏筛法-求n以内(0,n]有多少个素数的代码 // 复杂度:O(nloglogn) // Created by zbit on 2019/9/27. //测试用例: //1以内质数有0个 //2以内质数有1个 //5以内质数有3个 //100以内质数有25个 //1000以内质数有168个 //5000以内质数有669个

include

include

include

using namespace std; int sieve_num(int n) { vectoris_prime(n+1,true); vectorprime; int ans=0;

for(int i=2;i<is_prime.size();i++)
{
    if(is_prime[i])
    {
        prime.push_back(i);
        ans++;
        for(int j=i*2;j<is_prime.size();j+=i)
        {
            is_prime[j]=false;
        }
    }
}
return ans;

} int main() { int n;/ cin >> n; cout<<sieve_num(n)<<endl; return 0; }

顺带说一句,C++标准库中仅提供了求以10(log10())和以e(log())为底的函数,如果要求以任意底的对数,可以通过换底公式实现:
![](https://zbit.io/usr/uploads/2019/09/3802609019.png)
##区间筛法
上面讲的筛法都是从0开始的,但是如果我们需要求一个区间中的素数个数,又该如何解决呢?在文章的前半部分我们知道判断一个数是不是质数只需要判断到$\sqrt{n}$即可,换句话说,在一个区间[a,b)中,b内合数的最小质因数一定不超过$\sqrt{n}$,因此,我们只需要在[2,$\sqrt{n}$)中的筛得素数的同时,也将其倍数从待筛区间[a,b)中晒去,最后剩下的即为区间[A,B)内的素数。
代码实现:
```c++

//区间筛法-求区间[a,b)有多少个素数
//Created by zbit on 2019/9/27.
//复杂度:O(nloglogn)
//测试用例
//[22,37)内有三个素数,23 29 31
//[2,100)内有25个素数,2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

vector<ll>segment_sieve(ll a,ll b)
{
    vector<bool>is_prime(b+1,true);//is_prime[i]代表i是不是质数
    vector<ll>prime;//prime[i]代表区间[a,b)中有第[i]个素数
    is_prime[0]=is_prime[1]= false;//初始化特殊情况,保证初始最小的数是质数
    for(ll i=2;i*i<b;i++)//从i开始到sqrt(i)结束
    {
        if(is_prime[i])//检查是不是质数
        {
            for(ll j=i*2;j<is_prime.size();j+=i)
            {
                is_prime[j]=false;
            }
        }
    }
    vector<ll>re;
    for(ll i=a;i<b;i++)
    {
        if(is_prime[i]==true)re.push_back(i);
    }
    return re;

}
int main()
{
    int a,b;
    cin>>a>> b;
    vector<ll>ans=segment_sieve(a,b);
    for(ll i:ans)cout<<i<<" ";
    cout<<endl;
    cout<<"size:"<<ans.size();

    return 0;
}

快速幂取模

参考资料

1.[日]秋叶拓哉,[日]岩田阳一 [日]北川宜稔 《挑战程序设计竞赛 第二版》人民邮电出版社 2.[美]葛立恒,[美]高德纳,[美]帕塔许尼克 《具体数学:计算机科学基础(第2版)》人民邮电出版社 人民邮电出版社 3.素数定理-维基百科,自由的百科全书 4.埃拉托斯特尼筛法-素数定理-维基百科,自由的百科全书 5.奇妙的素数-素数定理-刘升平的文章 - 知乎 6.判断N是否是质数,为什么判断到根号N就可以了?-刘明的回答-知乎 5.C++以自定义底的对数函数 6.没有math.h我们能干啥-王希的文章-知乎

Last modification:October 8th, 2019 at 02:42 pm
如果觉得我的文章对你有用,请随意赞赏