How to find the dividers of a number quickly

It is possible to optimize looping to perform the calculation of dividers more efficiently:

• setting the c counter to 2,
• the beginning of the cycle as 2,
• the end for the square root of num plus 1 ( sqrt(num)+1 ),
• and adding 1 to the counter c at each iteration if the divisor is the root itself, or 2 if it is not.

looping looks like this:

c = 2;
for(i=2; i<((int)floor(sqrt(num)))+1; i++)
{
   if(num % i == 0)
   {
      c += (num/i == i) ? 1 : 2;
   }
}

Explaining: For each divisor i less than the square root, there is a reciprocal num/i greater than the square root.

Example: divisors of 64:

1
2
4
8   <== raiz quadrada
16  <== recíproco 64/4
32  <== recíproco 64/2
64  <== recíproco 64/1

Running the program without optimization for num=10^10 :

Tempo total = 132.3230133580 segundos
número de divisores e 121

With optimization, time significantly reduces (also for num=10^10 ):

Tempo total = 0.0014944220 segundos
número de divisores e 121

The explanation for the increase in performance is the change in the complexity of O (n) to O (sqrt (n)) , that is, looping will count up to 100,000 instead of 10,000,000,000.

Times were measured using the clock_gettime () function.

The full program used for testing follows:

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

int main()
{
  struct timespec inicio, fim;
  double demora;
  long long int num=10000000000, i;
  int c;

  clock_gettime(CLOCK_MONOTONIC, &inicio); // início do cronômetro
#if 0
  // Algoritmo original
  c = 0;
  for(i=1; i<=num; i++)
  {
     if(num%i==0)
     {
        c+=1;
     }
  }
#else
  // Algoritmo otimizado
  c = 2;
  for(i=2; i<((int)floor(sqrt(num)))+1; i++)
  {
     if(num%i==0)
     {
        c += (num/i == i) ? 1 : 2;
     }
  }
#endif
  clock_gettime(CLOCK_MONOTONIC, &fim); // fim do cronômetro
  demora = (fim.tv_sec - inicio.tv_sec) + (fim.tv_nsec - inicio.tv_nsec)/1E9;
  printf("Tempo total = %.10lf segundos\n", demora);
  printf ("número de divisores e %d",c);
}

tested with gcc version 8.1.0 - MinGW-W64

I did it this way and it was pretty fast:

//Utilizei como teste o seu comentário que o maior número seria 10^9
int number = 1000000000;
int count = 1;
int pow = 0;
int lastDivisor = 2;

for (int i = 2; number > 1; i++)
{
    if (number % i == 0)
    {
        bool isPrime = true;

        //Verifica se o número é primo (caso não seja, não serve para nós)
        for (int j = 2; j < i; j++)
        {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            if (lastDivisor == i) {
                //Enquanto a sequência se repetir (2,2,2), soma mais um no expoente (Ex.: 2³)
                pow++;
            }
            else { //Caso a sequência mude (Ex.: 2,2,2,3), faz o produto dos expoentes.
                count *= (pow + 1);
                lastDivisor = i;
                pow = 1;
            }

            number /= i;
            i = 1;
        }
    }
}
count *= (pow + 1);
printf("%d", count);

I used Prime Factor Decomposition to get the amount of dividers. If you want something "faster", you can try implementing the Atkin Sieve .