How to find splitters of a number quickly

Question

I have to ask a question that calculates the very large number dividers and needs in a fast way without being the conventional way, could help me My code

 #include<stdio.h>
 int main()
 {
  int num=19000,i,c=0;
  for(i=1;i<=num;i++)
  {
     if(num%i==0)
     {
        c++;
     }
  }
  printf ("número de divisores e %d,c)

 }

Answer 1

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

• defining the counter c like 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 each iteration if the divisor is the root itself, or 2 if it is not.

The looping gets that way:

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 divider i less than the square root, there is a reciprocal num/i larger than the square root.

Example: dividers 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 reduces significantly (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) for O(sqrt(n)), i.e., the looping will count up to 100,000 instead of 10,000,000.

Times were measured with the function clock_gettime().

Below is the full program used for the test:

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

Answer 2

I did it this way and it was pretty quick:

//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 Decomposition into prime factors to get the number of splitters. If you want something "faster", you can try to implement the Sieve of Atkin.