c++ - 你能给我解释一下这段代码吗？为什么 C++ 素数可以工作？

Question

此代码用于查找从 3 到 n 的素数，n 是输入。这段代码工作完美，但我需要更清楚地理解它，主要是嵌套 for 循环中的部分。

 #include <iostream>


using namespace std;



int main () 
{
cout << "Please enter a number: \n";
int inputtedNumber;
cin >> inputtedNumber;
cout <<"the primes between 3 and that number are: \n";
int candidate = inputtedNumber;

 for (int i=3; i<candidate; i++) 
 {
    bool prime=true;
    for (int j=2; j*j<=i;j++)
    {
        if (i % j == 0) 
        {
            prime=false;
            break;    
        }
    }   
    if(prime) cout << i << "\n";
 }

    system("pause");
  return 0;
 }


  thank you!

Answer 1

内部循环查看从 2 到 i 的平方根的每个数字，以查看 i 是否可以被该数字整除。如果 i 可以被 j 整除，则 i%j 将为零。如果它找到一个除数，那么我们就知道它不是质数并且可以停止寻找。

没有必要超越平方根，因为如果有一个比它大的除数，则必须也有一个比它小的相应除数，这个循环已经找到了。