Использование циклов while для нахождения наименьшего делителя числа

Question

Я снова изучаю программирование на С, используя мой учебник "Как программировать на 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);
    }
}