素数:修订间差异

来自吾萌百科
 
(未显示同一用户的5个中间版本)
第1行: 第1行:
{{未完成|Rmolives}}
若一个正整数无法被除了1和它自身以外的任何自然数整除,则称该数为'''素数(Prime number)''',或称'''质数'''。
若一个正整数无法被除了1和它自身以外的任何自然数整除,则称该数为'''素数(Prime number)''',或称'''质数'''。


第5行: 第4行:


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


<syntaxhighlight lang="c" line>
<syntaxhighlight lang="c" line>
第11行: 第10行:
if (n < 2)
if (n < 2)
return 0;
return 0;
for (int i = 2; i < sqrt(n); ++i)
for (int i = 2; i * i < n; ++i)
if (n % i == 0)
if (n % i == 0)
return 0;
return 0;
return 1;
return 1;
}
</syntaxhighlight>
== 筛法 ==
=== Eratosthenes筛法 ===
给定一个整数N,求出1~N之间的所有素数,称为素数的筛选问题。
对于这类问题我们有一种选择是'''Eratosthenes筛法'''。
Eratosthenes筛法基于这样的想法:任意整数x的倍数2x,3x,...都不是素数。根据素数的定义,上述命题显然成立。
我们可以从2开始,由小到大扫描每个数x,把它的倍数标记为合数。当扫描到一个数时,若它没被标记,说明它不能被2~x-1之间的任何数整除,该数就是素数。
<syntaxhighlight lang="c" line>
int v[MAX_N];
void eratosthenes(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;
}
}
</syntaxhighlight>
Eratosthenes筛法的时间复杂度为<math>O(N \log \log N)</math>,该算法实现简单,效率已经非常接近线性,是算法竞赛最常用的素数筛法。
=== 线性筛 ===
即使在优化后(从<math>x^2</math>开始),Eratosthenes筛法仍然会重复标记合数。
线性筛法通过“从大到小累计素因数”的方式标记每个合数。
设数组v记录每个数的最小素因数,我们按照以下步骤维护v:
# 依次考虑2~N之间每个数i。
# 若v[i]=i,说明i是素数,把它保存起来。
# 扫描不大于v[i]的每个素数p,令v[i*p]=p。
每个合数i*p只会被它的最小素因数p筛一次,时间复杂度为<math>O(N)</math>。
<syntaxhighlight lang="c" line>
int v[MAX_N], prime[MAX_N];
int m;
void primes(int n) {
memset(v, 0, sizeof(v));
m = 0;
for (int i = 2; i <= n; ++i) {
if (v[i] == 0) {
v[i] = i;
prime[++m] = i;
}
for (int j = 1; j <= m; ++j) {
if (prime[j] > v[i] || prime[j] > m/i)
break;
v[i * prime[j]] = prime[i];
}
}
}
}
</syntaxhighlight>
</syntaxhighlight>


== 参考资料 ==
== 参考资料 ==
# 算法竞赛进阶指南,李煜东,134~135页
# 算法竞赛进阶指南,李煜东,134~137页
[[Category:数学]]
[[Category:数学]]

2022年2月24日 (四) 15:46的最新版本

若一个正整数无法被除了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 * i < n; ++i)
		if (n % i == 0)
			return 0;
		return 1;
}

筛法

Eratosthenes筛法

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

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

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

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

int v[MAX_N];
void eratosthenes(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;
	}
}

Eratosthenes筛法的时间复杂度为[math]\displaystyle{ O(N \log \log N) }[/math],该算法实现简单,效率已经非常接近线性,是算法竞赛最常用的素数筛法。

线性筛

即使在优化后(从[math]\displaystyle{ x^2 }[/math]开始),Eratosthenes筛法仍然会重复标记合数。

线性筛法通过“从大到小累计素因数”的方式标记每个合数。

设数组v记录每个数的最小素因数,我们按照以下步骤维护v:

  1. 依次考虑2~N之间每个数i。
  2. 若v[i]=i,说明i是素数,把它保存起来。
  3. 扫描不大于v[i]的每个素数p,令v[i*p]=p。

每个合数i*p只会被它的最小素因数p筛一次,时间复杂度为[math]\displaystyle{ O(N) }[/math]

int v[MAX_N], prime[MAX_N];
int m;
void primes(int n) {
	memset(v, 0, sizeof(v));
	m = 0;
	for (int i = 2; i <= n; ++i) {
		if (v[i] == 0) {
			v[i] = i;
			prime[++m] = i;
		}
		for (int j = 1; j <= m; ++j) {
			if (prime[j] > v[i] || prime[j] > m/i)
				break;
			v[i * prime[j]] = prime[i];
		}
	}
}

参考资料

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