在while循环中使用sqrt函数，不明白

Question

我目前正在阅读《C++ Without Fear，第三版》。我对这段代码有点困惑，我理解如何使用

if

语句来确定

n

是否可以被

i

整除。我只是不明白

while

循环的意义是什么。

当然，你可以在没有它的情况下编写代码，如果

if

循环返回一个余数，那么它将是一个素数，否则它将不是一个素数。

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int n = 0; // Number to test for prime-ness
    int i = 2; // Loop counter
    bool is_prime = true;   // Boolean flag...
                            // Assume true for now

    // Get a number from the keyboard
    cout << "Enter a number and press ENTER: ";
    cin >> n;

    // Test for prime by checking for divisibility
    // by all whole numbers from 2 to sqrt(n).

    while (i <= sqrt(n)){
        if (n % i == 0) {       // If i divides n,
            is_prime = false;   // n is not prime
            break;              // BREAK OUT OF LOOP NOW!
        }
        ++i;                    // Add 1 to i.
    }

    // Print results

    if (is_prime) {
        cout << "Number is prime." << endl;
    } else {
        cout << "Number is not prime." << endl;
    }
    return 0;
}

我不太明白，请帮助我。

Answer 1

对于高效检查至关重要。

while 循环迭代 n 的潜在约数，从 2 开始一直到 sqr(n)。这是测试素数的有效方法，因为： [1] 不是检查从 2 到 n-1 的所有数字，而是检查 sqr(n) 减少了迭代次数；如果数字 n 的除数大于 sqr(n)，则相应的余除数必须小于 sqr(n)。 [2] 通过检查 sqr(n) 之前的所有可能除数，您可以确保如果 n 是合数，您将找到此范围内的除数，如果找不到除数，则 n 是质数。

如果删除 while 循环并仅使用 if 语句，则需要显式列出所有潜在的除数，这是不切实际且低效的。 while 循环提供了一种系统的方法来检查所有必要的除数，直到 sqr(n)