Algorithm to find all the exact divisors of a given integer

Question

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?

Solution 1

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.

Solution 2

Finding all divisors by using "finding all prime factors" in C (faster) and up to 18 digits.

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

unsigned int FindDivisors(unsigned long long divisors[], unsigned long long N) {
    unsigned int lastdiv = 0;
    divisors[lastdiv++] = 1;
    unsigned long long powerfactor = 1;
    unsigned long long number = N;
    while ((number & 1) == 0) {
        powerfactor <<= 1;
        divisors[lastdiv++] = powerfactor;
        number >>= 1;
    }

    unsigned long long factor = 3; unsigned long long upto = lastdiv;
    powerfactor = 1;
    while (factor * factor <= number) {
        if (number % factor == 0) {
            powerfactor *= factor;
            for (unsigned int i = 0; i < upto; i++)
                divisors[lastdiv++] = divisors[i] * powerfactor;
            number /= factor;
        }
        else {
            factor += 2; upto = lastdiv;
            powerfactor = 1;
        }
    }

    if (number > 1) {
        if (number != factor) {
            upto = lastdiv;
            powerfactor = 1;
        }
        powerfactor *= number;
        for (unsigned int i = 0; i < upto; i++)
            divisors[lastdiv++] = divisors[i] * powerfactor;
    }
    return lastdiv;
}

int cmp(const void *a, const void *b) {
    if( *(long long*)a-*(long long*)b < 0 ) return -1;
    if( *(long long*)a-*(long long*)b > 0 ) return 1;
    return 0;
}

int main(int argc, char *argv[]) {
    unsigned long long N = 2;
    unsigned int Ndigit = 1;
    if (argc > 1) {
        N = strtoull(argv[1], NULL, 10);
        Ndigit = strlen(argv[1]);
    }
    unsigned int maxdiv[] = {1, 4, 12, 32, 64, 128, 240, 448, 768, 1344,
                             2304, 4032, 6720, 10752, 17280, 26880, 41472, 64512, 103680};

    unsigned long long divisors[maxdiv[Ndigit]];
    unsigned int size = FindDivisors(divisors, N);
    printf("Number of divisors = %u\n", size);

    qsort(divisors, size, sizeof(unsigned long long), cmp);
    for (unsigned int i = 0; i < size; i++)
        printf("%llu ", divisors[i]);
    printf("\n");

    return 0;
}

Solution 3

The simple linear search can be improved by first throwing out all factors of 2. That can be done by simple bit shifting, or count training zero's with a nice intrinsic function. That's very fast in either case. Then run the algorithm suggested by shg (which will run much faster now that the powers of two aren't present), and combine the result with all the possible powers of two (don't forget this step). It helps a lot for inputs that have a lot of training zero's, but it even helps if they don't - you wouldn't have to test any even divisors anymore, so the loop becomes half as long.

Throwing out some constant low factors (but bigger than 2) can also help. Modulo with a constant is almost certainly optimized by the compiler (or if not, you can do it yourself), but more importantly, that means there are fewer divisors left to test. Don't forget to combine that factor with the divisors you find.

You can also factorize the number completely (use your favourite algorithm - probably Pollard's Rho would be best), and then print all products (except the empty product and the full product) of the factors. This has a good chance of ending up being faster for bigger inputs - Pollard's Rho algorithm finds factors very quickly compared to a simple linear search, there are usually less factors than proper divisors, and the last step (enumerating the products) only involves fast math (no divisions). This mostly helps for numbers with very small factors, which Rho finds the quickest.

Solution 4

This is my new C# Version. Thanks to Rndm it is almost 50 times faster than my first try.

public static long GetDivisors(long number)
    {
        long divisors = 0;

        long boundary = (long)Math.Sqrt(number);

        for (int i = 1; i <= boundary; i++)
        {
            if (number % i == 0)
            {
                divisors++;
                if(i != (number / i))
                {
                    if (i * i != number)
                    {
                        divisors++;
                    }
                }
            }
        }

        return divisors;
    }

View more solutions