素数

来自吾萌百科
Rmolives讨论 | 贡献2022年2月21日 (一) 15:48的版本
Exclamationdiamond blue.svg
提示
本页面尚未完成,作者Rmolives仍在继续编辑,请不要对此页面进行大幅度的改动。

若一个正整数无法被除了1和它自身以外的任何自然数整除,则称该数为素数(Prime number),或称质数

在整个自然数集合中,素数的数量不多,分布比较稀疏,对于一个足够大的整数N,不超过N的素数大约有[math]\displaystyle{ \frac{N}{\ln N} }[/math]个。

质数的判定

最简单的方法就是试除法,它作为最简单也最经典的确定性算法,是我们经常会使用的方法。

int is_prime(n) {
	if (n < 2)
		return 0;
	for (int i = 2; i < sqrt(n); ++i)
		if (n % i == 0)
			return 0;
		return 1;
}

Eratosthenes筛法

给定一个整数N,求出1~N之间的所有素数,称为素数的筛选问题。

对于这类问题我们有一种选择是Eratosthenes筛法

Eratosthenes筛法基于这样的想法:任意整数x的倍数2x,3x,...都不是素数。根据素数的定义,上述命题显然成立。

我们可以从2开始,由小到大扫描每个数x,把它的倍数标记为合数。当扫描到一个数时,若它没被标记,说明它不能被2~x-1之间的任何数整除,该数就是素数。

void eratosthenes(int* v, int n) {
	memset(v, 0, sizeof(v));
	for (int i = 2; i <= n; ++i) {
		if (v[i])
			continue;
		for (int j = i; j <= n/i; ++i)
			v[i * j] = 1;
	}
}

参考资料

  1. 算法竞赛进阶指南,李煜东,134~135页