提示
本页面尚未完成，作者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;
}
}
参考资料
- 算法竞赛进阶指南，李煜东，134~135页