Algorithm to find all the exact divisors of a given integer

jairaj picture jairaj · Jul 28, 2012 · Viewed 53.6k times · Source

I want to find all the exact divisors of a number. Currently I have this:

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i<=n/2)
    {
        if(n%i==0)
                  printf("%d,",i);
        i++;
     }
   getch();
}

Is there any way to improve it?

Answer

Rndm picture Rndm · Jul 28, 2012

First, your code should have the condition of i <= n/2, otherwise it can miss one of the factors, for example 6 will not be printed if n=12.

Run the loop to the square root of the number (ie. i <= sqrt(n)) and print both i and n/i (both will be multiples of n).

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}

Note :

  • For a perfect square, so that the square root is not printed twice, the additional checking is done at the end of loop for i*i == n as suggested by @chepner.
  • If you want all the factors in ascending order store the values in an array then at the end of the loop sort all the numbers and display.