埃拉托斯特尼筛法
埃拉托斯特尼筛法
埃拉托斯特尼筛法（，），简称-{zh-cn:埃氏筛; 埃氏筛; 爱氏筛，是一种用来质数的筛法，得名于古希腊数学家埃拉托斯特尼。其基本步骤是从最小的质数2开始，将该质数的所有倍数标记成合数，而下一个尚未被标记的最小自然数3即是下一个质数。如此重复这一过程，将各个质数的倍数标记为合数并找出下一个质数，最终便可找出一定范围内所有质数。
埃拉托斯特尼筛法可能在埃拉托斯特尼的时代之前就已经为人所知:14，并记载于另一位古希腊数学家尼科马库斯的《》中，尽管该著作中的这一筛法是从3开始，从奇数中依次筛去奇数的倍数，而非从自然数中筛去质数的倍数:242-243。
使用埃拉托斯特尼筛法找出120以内的所有质数。由于112=121>120，当11成为最小的未标记整数时，尚未标记的所有数皆可确认为质数。请注意到在标记时直接从每个质数的平方开始。
运用与示例.
埃拉托斯特尼筛法通过不断地标记当前质数的所有倍数为合数，从而取得最小的未标记整数为下一个质数。不过，在实际使用此筛法寻找一个范围内的质数时，不需要检查范围内所有整数，也不需要对每个质数都标记其所有的倍数。
若要找出25以内的所有质数，使用如上述改进过的埃拉托斯特尼筛法的具体过程如下：
由此得到25内的质数为2，3，5，7，11，13，17，19，23。
以上的算法可用以下-{zh-cn:伪代码;虚拟码;表示：
-{zh-cn:
输入：整数"n" > 1
设"A"为布尔值矩阵，下标是2至"n"的整数，
初始时全部设成true。
for "i" = 2, 3, 4, ..., 不超过：
if "A"["i"]为true：
for "j" = "i2", "i2+i", "i2+2i", "i2+3i", ..., 不超过"n"：
"A"["j"] := false
输出：使"A"["i"]为true的所有"i"。;
输入：整数"n" > 1
设"A"为布尔值阵列，指标是2至"n"的整数，
初始时全部设成true。
for "i" = 2, 3, 4, ..., 不超过：
if "A"["i"]为true：
for "j" = "i2", "i2+i", "i2+2i", "i2+3i", ..., 不超过"n"：
"A"["j"] := false
输出：使"A"["i"]为true的所有"i"。;
埃拉托斯特尼筛法的时间复杂度为formula_16；相比之下，若是通过对范围内每个整数进行试除法来找出范围内的质数，则其时间复杂度为formula_17:13-14。
程式码.
Python 3.6-3.10.
def eratosthenes(n):
is_prime = [True] * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [x for x in range(2, n + 1) if is_prime[x]]
print(eratosthenes(120))
C语言.
int prime[100005];
bool is_prime[1000005];
int eratosthenes(int n) {
int p = 0;
for (int i = 0; i flag(upperbound + 1, true);
flag[0] = flag[1] = false; //exclude 0 and 1
for (int i = 2; i * i
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.