c++ - 埃拉托色尼筛法

Question

我正在解决euler项目中的一些编程问题，我在这个问题上停了下来:

生成质数

我理解算法，但我不理解解决方案中的一件事:

这是我从另一个讨论中得到的解决方案:

void sieve_of_eratosthenes(int n)
{
    bool *sieve = new bool[n+1];

// Initialize
sieve[0]=false;
sieve[1]=false;
sieve[2]=true;

for(int i=3;i<n+1;++i)
    sieve[i]=true;

// Actual sieve
for(int i=1; i<n+1; ++i)
    //**i didnt understood what is the purpose of this condition**
    if(sieve[i]==true)
        for(int j=2;j*i<n+1;++j)
            sieve[j*i]=false;

// Output
cout << "Prime numbers are: " <<endl;
for(int i=0;i<n+1;++i)
    if (sieve[i])
        cout << i <<endl;

delete [] sieve;

int main()
{
    int n = 70;
    sieve_of_eratosthenes(n);
}

我明白在这种情况下我们试图知道数字是否是素数，但我不明白为什么我们要跳过非素数

任何帮助都会对我有用，谢谢

Answer 1

效率。让我们看看合数 4。我们真的需要检查所有其他数字的整除性吗？不，因为我们已经检查了它的主要因素。

简而言之，检查合数是一个多余的过程，因为我们检查的是它的质因数。