编程小站



和我一起走进编程的世界

素数、素数筛和线性筛

如果你想要判断一个数字是否是质数,你该怎么办呢?

首先,我们要先知道质数的定义是什么:

质数是指,在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

那么我们很简单就能编辑出我们的最初版判断素数函数:【我们以欧拉第七题举例,输出第10001个素数】

#include <iostream>
#include <cmath>
#include <cstdio>//头文件
using namespace std;
#define MAXN 200000//一个宏定义,来定义最大值MAXN,方便修改
int prime[20000];
bool judge_prime(int x) {//声明一个函数,用来判断是否是质数
	for (int i = 2; i <= sqrt(i); i++) //循环到根号下i为止,因为i是最大值
    {
		if(x % i == 0)return false;//如果有除了2以外的数是他的因子,则不是质数
	}
	return true;//如果没有除了2以外的因子,则是质数
}

int main()
{
	int cnt = 0, i = 2;//声明一个变量cnt用于记录当前素数的个数,声明i为当前判断的数的值
	for(int i = 1; i <= MAXN; i++){//循环到MAXN结束
		if(judge(i)){//如果i是质数
			cnt++;//cnt++
			prime[cnt]=i;//把数组的第cnt位记为i
		}
	}
	cout << prime [10001];//输出标记数组里的第10001位,也就是第10001个素数。
	return 0;
}

懂了?

但是这样比较麻烦

我们还有下一种办法:素数筛

又称欧拉筛

我们利用素数来标记合数

因为合数一定有质因子

所以我们从最小的质数出发

标记所有它的倍数,到MAXN为止

然后i++,如果这个数字被标记过,那么它就是合数

如果这个数字没有被标记过,那么他就是质数

然后我们就要去标记他的倍数

以此类推。

话不多说,上代码!

#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 200000
int prime[MAXN];//声明一个prime[MAXN],且初识为0
void list_prime() {//声明一个
	for (int i = 2; i <= MAXN; i++) {//循环MAXN次
		if (prime[i])continue;//如果prime[i]中已经有了值(也就是被标记过),则直接进行下一个循环
		prime[0]++;//我们用prime数组的第0位来进行计数。所以这一步就是计数器++
		prime[prime[0]] = i;//primt[计数器]赋值为i(这个数的大小)
		for (int j = i * 2; j <= MAXN; j += i) {
			prime[j] = i;//标记i的倍数
		}
	}
	return;//结束函数
}

int main()
{
	list_prime();//调用我们的素数筛函数
	printf("%d\n", prime[10001]);//输出标记数组里的第10001位,也就是第10001个素数。
	return 0;
}

这个方法比上一个好了很多。

但是还有一个小问题:

很多数字标记了好几次,有不必要的时间开销。

比方说:

15这个数字,我们在3里面标记了一次;5里面也标记了一次。

所以,我们还能继续简化:

对于一个数字n,我们从2开始标记,每次往后移动一个质数,一直标记到n的最小质因数

也就是从2 * n一直到n的最小质因数 * n

然后n++,继续向下标记。

举个例子:

12345678910
11121314151617181920
21222324252627282930

从2开始,到2的最小质因数2。

也就是只标记一个2*2,等于4。

123 5678910
11121314151617181920
21222324252627282930

对于3,从2开始标记,标记到3的最小质因数3。

也就是标记一个3 * 2,3 * 3,即6和9。

123 5 78 10
11121314151617181920
21222324252627282930

对于4,我们从2开始标记,标记到4的最小质因数2。

也就是只标记一个2 * 4,即8。

123 5 7 10
11121314151617181920
21222324252627282930

对于5,我们从2开始标记,标记到5的最小质因数5。

也就是标记5 * 2,5 * 3,5 * 5,即10,15,25。

123 5 7
11121314 1617181920
21222324 2627282930

对于6,我们从2开始标记,标记到6的最小质因数2

也就是6 * 2,只有一个数字12。

123 5 7
11 1314 1617181920
21222324 2627282930

对于7,同理,标记14,21,35(但是我们只以前30个举例子,你可以理解为MAXN=30。后续将不再进行超出30的举例)

对于8,同理,标记16。

对于9,同理,标记18,27。

对于10,同理,标记20。

对于11,标记22;

对于12,标记24;

对于13,标记26;

对于14,标记28;

对于15,标记30。

然后我们发现,所有合数只被标记了一次,我们就得到了下面的素数表:

123 5 7
11 13 17 19
23 29

上代码!

#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 200000
int prime[MAXN+100];//声明一个数组,用来存储质数、声明质数
void list_prime() {//声明线性筛函数
	for (int i = 2; i <= MAXN; i++)//循环到MAXN停止
	{
		if (!prime[i])//因为prime[i]的初值位0,所以加了一个叹号。这样的话,被标记过为假,没被标记过为真
		{
			prime[0]++;//还是用prime[0]来做计数器,计数器++
			prime[prime[0]] = i;//把prime[计数器]赋值为i
		}

		for (int j = 1; j <=prime[0]; j++)
		{
			if (prime[j] * i > MAXN)break;//如果标记的值已经超过了MAXN,那就退出
			prime[prime[j] * i] = 1;//把 prime[j](用来标记的质数,从2(prime[i])开始,到最小质因数结束。) * i(用来标记的数字,也就是2、3、4、5....) 这一位标记为1。
			if (i % prime[j] == 0)break;//如果i % prime[j]为0,那prime[j]就不是最小质因数了,退出循环。
		}
	}
}

int main()
{
	list_prime();//调用这个函数
	cout << prime[10001];//输出他的第10001位
	return 0;
}
最近的文章

2.0 数组与指针

你知道计算机为什么有32位和64位之分吗?首先,计算机是以二进制进行运算和存储的。每一个变量,在计算机中,都有其唯一的“地址”,而这地址就是用二进制来存储的。一个0/1(二进制的一位)叫做一个比特(bit),八个比特叫做一个字节(b)。一千个字节叫做kb,简称k;一兆字节叫做mb,简称m;一千兆字节…

继续阅读
更早的文章

1.9 函数、递归与递推

函数相关知识点…

继续阅读