了解此嵌套的for循环以在C ++中显示质数

Question

我是编码的初学者，所以我对以下示例代码感到困惑，因为它们显示的质数小于20。

#include <iostream>
using namespace std;

int main () {
int i, j;

for(i = 2; i<20; i++) 
{
  for(j = 2; j <= (i/j); j++)
     if(i%j==0) break; 
     if(j > (i/j)) cout << i << " is prime\n";

}
return 0;
}

因此，对于第一个循环，i = 2，我首先选择具有j =2。然后，在第8行中，有if（i％j == 0）中断； i = j = 2确实满足此条件。那么为什么我的输出仍将2作为质数之一？

P.S。我确实知道2是质数，但是我不了解代码。谢谢。

Answer 1

for循环：

for(j = 2; j <= (i/j); j++)

j <= (i/j)时第一次不通过i = 2。

和：

 if(j > (i/j)) cout << i << " is prime\n";

不是该for循环的一部分。

Answer 2

如果我们这样重写您的代码：

for (i = 2; i < 20; i++)
{
    for (j = 2; j <= (i / j); j++)
    {
        if (i % j == 0) break;
    }
    if (j > (i / j)) cout << i << " is prime\n";
}

然后会更加清楚，break仅会跳出内循环，然后下一行（打印2）将被执行。

Answer 3

2到n / 2之间的因数，以检查是否为质数

#include <iostream>
using namespace std;

int main () {
 int i, j;

 for(i = 2; i<20; i++)
{
  for(j = 2; j <= (i/2); j++)
   if(i%j==0) break;
 if(j > (i/2)) cout << i << " is prime\n";

}
 return 0;
}

Answer 4

关于此代码的另一个有趣的事实是为什么，您只需要查找i/j就可以找到素数。这是因为复合数的素数不大于其平方根（demonstration）。

因此，基本上j仅从2升至sqrt(i)。

如果将for条件从j <= i/j更改为j*j <= i，也可以清除代码。为什么？因为i/j是整数除法，所以您需要额外的条件if(j > (i/j))。因此，最终的代码将是：

#include <iostream>
using namespace std;

int main () {
  int i, j;

  for(i = 2; i<20; i++) 
  {
    for(j = 2; j*j <= i; j++)
       if(i%j==0) break; 
    cout << i << " is prime\n";

  }
  return 0;
}