c - 使用 While 循环查找数字的最小除数

Question

我使用《C 如何编程》教科书再次学习 C 编程。作为文本中的练习，系统提示我查找用户提供的数字的最小除数。澄清一下，以防万一，如果除法结果余数为 0，则数字就是除数，并且我们正在寻找大于 1 的除数。为了完成此操作，它指示我应该使用 while 循环。我刚刚开始使用 while 循环，所以我了解基本思想和功能，但不完全了解如何在这种情况下正确执行所有操作。看到这个例子会让我有更好的理解。我认为我应该创建一些寻找除数的代码，一直计数直到找到除数。感谢您提供的任何帮助。非常感谢。

最诚挚的问候!

Answer 1

要找到最小除数，您需要检查从 2 到 n 中哪个数字除以余数为 0。第一个除以余数为 0 的数是最小的数。请参阅下面的实现:

int n, i;
scanf("%d", &n);

i = 2;
while(i <= n){
    if(n % i == 0){
        printf("The smallest number is %d\n", i);
        break;
    }
    i++;
}

但是你可以更有效地做到这一点。您实际上不需要遍历直到n。遍历直到 n 的平方根就足以找到这个。如果遍历到n的平方根后仍未找到最小的数，则说明最小的数就是n本身。请参阅下面的实现。

#include <stdio.h>
#include <math.h>

int main()
{
    int n, i, sq;
    scanf("%d", &n);

    i = 2;
    sq = sqrt(n);
    while(i <= sq){
        if(n % i == 0){
            printf("The smallest number is %d\n", i);
            break;
        }
        i++;
    }
    if(i > sq){
        printf("The smallest number is %d\n", n);
    }
}