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为零。如果它找到一个除数，那么我们知道它不是素数并且可以停止查找。

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

Answer 2

这条线是关键。

    if (i % j == 0) 

如果可以被 整除，则执行该if块，这意味着它不是素数。iji

Answer 3

for (int i=3; i<candidate; i++)  // for every i between 3 and candidate
{
    bool prime=true;
    for (int j=2; j*j<=i;j++)  // for every j between 2 and the square root of i
    {
        if (i % j == 0) // if there is an i that is evenly divisible by j
        {
            prime=false; // set the flag
            break;    // break the inner loop
        }
    }   
    if(prime) cout << i << "\n"; // if i was a prime (no j's were evenly divisible), print it
}