Using While-Loops to Find the Smallest Divisor of a Number

Question

I've been studying C programming again with the usage of my "C How to Program" textbook. As an exercise within the text, I have been prompted to find the smallest divisor of a number supplied by a user. Just to clarify, just in case, a number is a divisor if the division results in a remainder of 0, and we are looking for a divisor greater than 1. To complete this, it instructs that I should use a while-loop. I have just begun using while-loops, so I understand the basic idea and function, but not exactly how to execute everything properly in this situation. Seeing this example will grant me a better understanding. I take it as that I am supposed to create some code that looks for a divisor, counting up until it finds one. Thank you for any help that you provide. It is greatly appreicated.

Best regards!

https://www.tutorialspoint.com/cprogramming/c_while_loop.htm — OldProgrammer, Feb 25 '19 at 22:11
The important part is to consider what the condition of your loop will be, and for that I suggest looking at this [question](https://stackoverflow.com/questions/6993982/how-to-find-the-remainder-of-a-division-in-c). — Michael, Feb 25 '19 at 22:15

score 2 · Accepted Answer · answered Feb 25 '19 at 22:34

To find the smallest divisor, you need to check from 2 to n that which number's division results in a remainder of 0. The first number which division results in a remainder of 0 is the smallest one. See the implementation below:

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++;
}

But u can do it more efficiently. you don't actually need to traverse till n. Traversing till square root of n is enough to find this. if you don't find the smallest number after traversing till the square root of n that's mean the smallest number is n itself. see the implementation below.

#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);
    }
}

Using While-Loops to Find the Smallest Divisor of a Number

1 Answers1