Eratosthenes筛

介绍：

Eratosthenes筛子是一种简单而有效的算法，可以为给定的一组极限找到素数。

算法的工作：

算法的工作非常简单。

步骤1：首先，我们将所有数字记为2到n。
步骤2：从第一个素数开始“2”，我们删除/删除所有可被2整除的数字，直到“n”.
步骤3：然后转到下一个质数，现在找出可以被当前质数整除的数，直到当前质数的平方。
步骤4：重复步骤3，直到结束。
步骤5：您将获得所有素数的列表。

使用示例了解Eratosthenes筛网：

在此示例中，我们需要2至30的所有质数。下面借助图像，我解释了上述步骤。

步骤1：将所有数字记为2到n。

步骤2：从号码“2”，删除2的所有倍数。这里我们以红色表示删除。

步骤3：然后转到下一个质数，现在找出可以被当前质数整除的数，直到当前质数的平方。下一个素数是3’s的平方是9。因此，请剔除3到9的倍数的所有数字。由于早已剔除6，所以现在剔除9。

重复步骤3，直到结束。我们将再尝试一遍。

现在下一个素数是“5”, it’s的平方是25。删除所有5到25的倍数的数字。“10”, “15”, “20”, “25”. As “10” and “20”已经被淘汰，被淘汰“15” and “25”

最后，我们将剩下以下数字。

用C ++实现

为了用C ++实现，我们采用大小为n的布尔数组并将所有字段标记为true。然后，我们应用上述步骤，而不是将其删除，而是将椎旁细胞设为假。最后，我们写下所有的单元格索引为真。

#include <iostream>

using namespace std;

void sieve_of_eratosthenes(int n)
{
    //take a boolean array to store which index is a prime number.
    bool prime[n + 1];

    // make all the cells as true.
    for (int i = 2; i <= n; i++) 
    { 
        prime[i] = true; 
    } 

    // from the first prime number
    for(int j = 2; j*j <= n; j++)
    {
        // check if the current index is a prime number, if 是, then 
        if(prime[j] == true)
        {
            //if 是, then make all the cless that are multiple of that index as false
            for(int i = j*2; i <= n; i += j)
            {
                prime[i] = false;
            }
        }
    }

    cout<<" All the prime numbers from 2 to 30 is "<<endl;
    // from the first prime number, print all the prime numbers.
    for(int j = 2; j <= n; j++)
       if(prime[j]) // if prime[j] is true, then it is a prime number. Print it
          cout << j << " ";
}

int main()
{
    // n is the max limit to find the list of prime numbers from
    int n = 30;
    sieve_of_eratosthenes(n);
    return 0;
}

输出量

2 3 5 7 11 13 17 19 23 29

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：