求素数个数的总结

发表于 | 分类于

求素数个数的总结

前言

最近刷题的时候碰到素数问题还是蛮多的，基本上核心的问题都是围绕如何求素数的个数,下面就根据：

给出一个正整数n(n<=10^5),求不大于n的素数的个数。

来讨论解法。

解法一:嵌套循环

第一个解法总是最朴实的，算是对下面的一个抛砖引玉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
\\c++实现
#include<iostream>
#include<algorithm>
#include<time.h>
using namespace std;
int main(){
    int cnt,sum=0; //cnt储存总数
    cin >> cnt;
    for(int i = 2;i<=cnt;i++){
        int ok = 1;
        for(int z = 2;z<i;z++){
            if(i%z == 0){ok = 0;break;}
        }
        if(ok == 1){sum++;}
    }
    cout << sum << endl;
    cout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << endl; //记时
}

1
2
3
4
5
输入
100000
输出
9592
Time used = 1.41

用时是1.41秒,下面我们看解法二。

解法二

观察素数的生成规律不难发现，其实正整数的公因子是对称的，出现必定成对出现，而且中间的值就是√n,也就是说，我们不必去遍历每个值，只需要遍历小于等于√n的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
\\c++实现
#include<iostream>
#include<algorithm>
#include<time.h>
using namespace std;
int main(){
    int cnt,sum=0; //cnt储存总数
    cin >> cnt;
    for(int i = 2;i<=cnt;i++){
        int ok = 1;
        for(int z = 2;z*z<=i;z++){  //将z<i改成了z<=i
            if(i%z == 0){ok = 0;break;}
        }
        if(ok == 1){sum++;}
    }
    cout << sum << endl;
    cout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << endl; //记时
}
1
2
3
4
5
输入
100000
输出
9592
Time used = 0.019

可以看出时间从1.41直接到了0.019。那么有没有更加简便的方法呢，请看解法三。

解法三：

从解法二的角度来看，我们已经成功的将算量缩减到了遍历√n的程度，那么还有什么规律可以找吗?

我们用解法二对17进行验证。分别要验证的数字是2,3,4–其中2,3为素数，4为合数。

我们可以发现,如果17可以被4整除，那么必定可以被2整除。
也就是说,判断的条件可以再简单一点—-<=√n && ==素数。
我们需要一个vector储存前面已经得出的素数,然后用这些素数去验证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//c++实现 
#include<iostream>
#include<algorithm>
#include<time.h>
#include<vector>

using namespace std;

vector<int> ve; //储存素数

int main(){
    int cnt,sum=0; //cnt储存总数
    cin >> cnt;
    for(int i = 2;i<=cnt;i++){
        int ok = 1;
        for(auto x = ve.begin();x != ve.end() && (*x)*(*x) <= i;x++){
            if(i%(*x) == 0){ok = 0;break;}
        }
        if(ok == 1){ve.push_back(i);sum++;}
    }
    cout << sum << endl;
    cout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << endl;
}

1
2
3
4
5
输入
100000
输出
9592
Time used = 0.018

时间上与二没有太大区别，但是在内存使用上，还是缩减了不少。
好啦，那么素数算法就到这儿了?
实际上上述几种都可以被归为一类—除法(也就是用数去除去验证),另外还有一种筛法。见解法四。

解法四:筛法

与上述的除法不同，筛法的思想是通过已有的素数，然后将他们的倍数(合数)在范围中筛去,从而最后得到所有的素数,具体的思想大家可以看维基百科-埃拉托斯特尼筛法，下面我用c++实现一下(其实是维基百科里的-。-,那里面有点小bug)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
#include<time.h>
#include<vector>
#include<string.h>
using namespace std;
#define MAXN 100020
bool flag[MAXN];


int main(){
    long maxn,cnt = 0;
    for(long i = 0;i<MAXN;i++){flag[i] = 1;}
    cin >> maxn;
	flag[0]=0;            //0不是素数
	flag[1]=0;            //1不是素数
	for(long i = 2;i*i<=maxn;++i)
	{  
        /*当i为素数时，i的所有倍数都不是素数*/
		if(flag[i])
		{
			for(long j = i*i;j<=maxn;j+=i)
			{
				flag[j]=false;
			}
		}
	}
    for(long i = 0;i<maxn;i++){
        if(flag[i]){cnt++;}
    }
    cout << cnt << endl;
    cout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << endl; //记时
    return 0;
}

1
2
3
4
5
输入
100000
输出
9592
Time used = 0.001

筛法一出，谁与争锋？

开个玩笑哈哈，不过大家可以看到，从除法到筛法又有了进一步的突破。而这儿的筛法也不是最优的，因为大家可以看到还是会有重叠的地方，所以就单单素数就有这么多种的求解方法。我认为学无止境，而深浅则根据自身环境去定夺。

补充:

再说点素数的小知识点,上面的题目是求到n为止，也就是说范围给出。那么题目中如果说求n个素数。也就是说具体到哪儿我们其实是不清楚的。
那么一个方法就是用可以拓展的容器vector这种，不过大家都知道，既然都讲到这儿了那么势必是要追求效率的。

这时候就应该素数定理出场了，素数的分布是有规律可循的。按常识来看，素数的分布是越往后越稀少，素数定理就是对素数在某个范围内的估计。最简洁的就是x/ln(x),假设要估计1,000,000以内有多少质数，用该公式算出是72,382个，而实际有78,498个，误差约8个百分点。该公式的特点是：估算的范围越大，偏差率越小。这样就可以通过素数定理反推范围了，因为有误差，所以一般将范围扩大15%左右即可。

参考

本文的后面的筛法和素数定理都是参考编程随想大哥的,有梯子的可以上去看看。开阔眼界。
附上连接
编程随想