我正在解决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);
}
我知道在这种情况下,我们试图知道这个数是不是质数,但我不明白为什么我们要跳过非质数
任何帮助对我都有用,谢谢
最佳答案
效率。让我们看看复合数字4我们真的需要检查所有其他数字的可分性吗?不,因为我们已经检查了它的主要因素。
简而言之,检查复合数是一个多余的过程,因为我们检查它的素因子。