C Como encontrar os divisores de um número de forma rápida

[diogo moura]

#include <stdio.h>

int main()
{
	int n=4, cont=0,i;
	for(i=1;i<=4;i++)
	{
		if(n%i==0)
		{
			cont++;
		}
	}
	printf("%d", cont);
}

Esse é a forma que eu conheço tem outra maneira mais eficiente que essa ? 

[icarodantas123]

Eu conheço uma, você deve varrer somente até o número / 2.

 

Por exemplo, pra achar a quantidade de divisores de 10:

int cont = 1;

for (int i = 1; i <= 10/2; i++) {

  if (10 % 1 == 0) {

    cont++;

  }

}

 

[isrnick]

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

int main()
{
   int n, raiz_n;
   
   scanf("%d",&n);
   
   raiz_n = (int)sqrt(n);
   
   //Busca apenas até a raiz quadrada de n
   for(int i = 2; i < raiz_n; i++)
    {
        //Imprime 2 divisores de uma vez, i e n/i
        if(n % i == 0) printf("%d, %d, ", i, n/i);
    }
    //Se n for quadrado perfeito também imprime a raiz de n
    if(raiz_n * raiz_n == n) printf("%d,", raiz_n);
    
    printf("\n");
        
    return 0;
}

 

[diogo moura]

@isrnick me perdoe se eu estiver falando bobagem, mas por exemplo o número 4 possui os divisores 1 2 4, o no seu código só aparece 2 2 2, você poderia me explicar melhor o código

[isrnick]

@diogo moura Eu não estava incluindo 1 nem o próprio número, mas se quiser incluir basta fazer i começar em 1:

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

int main()
{
   int n, raiz_n;
   
   scanf("%d",&n);
   
   raiz_n = (int)sqrt(n);
   
   //Busca apenas até a raiz quadrada de n
   for(int i = 1; i < raiz_n; i++)
    {
        //Imprime 2 divisores de uma vez, i e n/i
        if(n % i == 0) printf("%d, %d, ", i, n/i);
    }
    //Se n for quadrado perfeito também imprime a raiz de n
    if(raiz_n * raiz_n == n) printf("%d,", raiz_n);
    
    printf("\n");
        
    return 0;
}

Não deve aparecer nenhum número repetido.

[diogo moura]

Fiz o que mandou só que não apareceu nenhum valor@isrnick, desculpe se estou sendo meio difícil de entender a sua solução

[isrnick]

No meu programa você é só rodar ele e digitar o número que quer testar e dar enter, e ele vai mostrar todos os divisores, eu testei aqui e funcionou perfeitamente.

[Ansi C]

7 horas atrás, isrnick disse:

No meu programa você é só rodar ele e digitar o número que quer testar e dar enter, e ele vai mostrar todos os divisores, eu testei aqui e funcionou perfeitamente.

Experimente digitar um número negativo, na realidade não deve funcionar porque não existe raiz real de número negativo.

 

Spoiler

#include <stdio.h>
// incluir os comando printf, scanf

int main (void){
    int denominador;
    int numerador;
    int limite;
    int step;
    // VARIAVEIS:
    // denominador = número inteiro divisor
    // numerador   = número inteiro divisível
    // limite      = o máximo divisor possível
    // step        = iteração de cada etapa de divisão
    
    scanf ("%d", &numerador);
    if (numerador < 0)
            numerador = -numerador;
    // pegar no qual investiga-se os divisores
    // verificar se é negativo (menor que 0), se sim então inverte sinal
    
    limite = numerador/2;
    if (numerador == limite*2)
            step = 1;
    else
            step = 2;
    denominador = 1;
    while (denominador <= limite){
            if (0 == numerador%denominador)
                    printf ("%d ",denominador);
            denominador += step;
            }
    // dirar que o limite é igual a metada do valor, isso é
    // verificar se é par, isso é importante porque não existe divisor
    // par para valores ímpares.
    // percorrer escaneando todos os possíveis módulos de divisão exatos.
  
    return 0;
    // fim do programa
    }

 

Por que eu acho que meu código mais rápido?

           Porque excluiu a verificação de valores pares para números ímpares.

[isrnick]

5 horas atrás, AnsiC disse:

Experimente digitar um número negativo, na realidade não deve funcionar porque não existe raiz real de número negativo.

Basta trocar o sinal do número antes de calcular a raiz.

 

5 horas atrás, AnsiC disse:

Por que eu acho que meu código mais rápido?

           Porque excluiu a verificação de valores pares para números ímpares.

Isso só deixa um pouco mais rápido se o número for ímpar, para números pares não há ganho.

 

Meu programa só precisa achar metade dos divisores (pois a outra metade é calculada usando a primeira), e o intervalo de busca é menor pois vai apenas até a raiz quadrada do número.

 

Mas vamos adicionar sua otimização à ele:

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

int main()
{
    int n, raiz_n;
    
    printf("Digite um número: ");
    scanf("%d",&n);
    n = n < 0 ? -n : n;
    
    raiz_n = (int)sqrt(n);
    
    //Busca apenas até a raiz quadrada de n
    for(int i = 1, a = (n%2 == 0 ? 1 : 2); i < raiz_n; i+=a)
    {
        //Imprime 2 divisores de uma vez, i e n/i
        if(n % i == 0) printf("%d, %d, ", i, n/i);
    }
    //Se n for quadrado perfeito também imprime a raiz de n
    if(raiz_n * raiz_n == n) printf("%d,", raiz_n);
    
    printf("\n");
    
    return 0;
}

Agora ele não busca mais divisores pares se o número for ímpar.

[Ansi C]

12 minutos atrás, isrnick disse:

Isso só deixa um pouco mais rápido se o número for ímpar, para números pares não há ganho.

Exatamente haverá ganho, e para números pares permanece normal. Como há imprevisibilidade entre pares e ímpares existe ganho. A ideia é explorar as possibilidade.

 

17 minutos atrás, isrnick disse:

Meu programa só precisa achar metade dos divisores (pois a outra metade é calculada usando a primeira), e o intervalo de busca é menor pois vai apenas até a raiz quadrada do número.

Não sei dizer ao certo o custo de calcular a raiz quadrada, porém acredito ser maior ou igual a repetição.

adicionado 2 minutos depois

Principalmente quando as operações se dão com números flutuantes (caso da raiz) que tem maior custo de processamento. 

adicionado 5 minutos depois

Em fim, tudo que sei me leva a crer que há maior ganho sem a raiz. 

Carecemos de teste para dar fim as hipóteses.

[isrnick]

@AnsiC A complexidade do sqrt() é O(log n) (fonte: https://stackoverflow.com/questions/23103847/what-is-the-time-complexity-of-the-following-function ), e a raíz é calculada 1 vez só.

 

Entretanto um aumento no número de ciclos que tem que ser rodados para achar os divisores aumenta o tempo linearmente ( O(n) ).

[Ansi C]

@isrnick Exemplo?

[isrnick]

55 minutos atrás, AnsiC disse:

@isrnick Exemplo?

 

2 programas testados e seus respectivos tempos de execução:

 

Sem raiz quadrada:

#include <stdio.h>
// incluir os comando printf, scanf

int main (void){
    int denominador;
    int numerador;
    int limite;
    int step;
    
    numerador = 10000000;
    
    for (int j=0; j < 10000; j++)
    {
        limite = numerador/2;
        
        for (denominador = 1, step = (numerador == limite*2 ? 1 : 2); denominador <= limite; denominador += step)
        {
            if (0 == numerador%denominador)
                printf ("%d ",denominador);
        }
        printf("%d\n", numerador);
    }
  
    return 0;
}

Process returned 0 (0x0)   execution time : 178.815 s

 

Com raiz quadrada:

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

int main()
{
    int n, raiz_n;
    
    n = 10000000;
    
    for (int j=0; j < 10000; j++)
    {
        raiz_n = (int)sqrt(n);
        
        for(int i = 1, a = (n%2 == 0 ? 1 : 2); i < raiz_n; i+=a)
        {
            if(n % i == 0)
                printf("%d %d ", i, n/i);
        }
        if(raiz_n * raiz_n == n) printf("%d", raiz_n);
        
        printf("\n");
    }
    
    return 0;
}

Process returned 0 (0x0)   execution time : 11.307 s

 

 

[Ansi C]

Percebo, mas não acredito que calcular a raiz exata envolve muitos processos lógicos e com muitas casas decimais, seja tão mais rápido. Estou muito surpreso com a agilidade da função raiz.

valeu

adicionado 3 minutos depois

Se bem que para base 10 me parece muito simples de ser feito, melhor seria que o numerador fosse escolhido "aleatoriamente".

[isrnick]

2 horas atrás, AnsiC disse:

Se bem que para base 10 me parece muito simples de ser feito, melhor seria que o numerador fosse escolhido "aleatoriamente".

Computadores fazem contas em base 2 não em base 10, ser em base 10 não dá vantagem, a menos que o algoritmo de calculo de raiz quadrada especificamente use alguma propriedade da base 10 para deixar o cálculo mais rápido? (Não me parece que seja o caso.)

 

E os 2 programas tem que usar o mesmo número para poder comparar os tempos.

 

Faça testes e veja se encontra algum que muda o resultado. Eu já fiz vários testes, testei com números com muitos divisores (ex: 20901888) e até com números primos (ex: 10000169), usando o método com a raiz quadrada foi bem mais rápido em todos os casos que testei.

[Ansi C]

1 hora atrás, isrnick disse:

Computadores fazem contas em base 2 não em base 10, ser em base 10 não dá vantagem, a menos que o algoritmo de calculo de raiz quadrada especificamente use alguma propriedade da base 10 para deixar o cálculo mais rápido? (Não me parece que seja o caso.)

Acredito que sim, é possível existir tabelas com resultados, ou matriz logarítmica. Algo semelhante a tabela de resultado para funções trigonométricas de quase todos os Ângulos. Isso explicaria rapidez para resolução de base 10, é puro calculo, nada de álgebra ou aritmética .  

[LuisOPsum]

Olá...

Esse mostra todos os divisores.:

#include <stdio.h>
int main()
{
    int cont=0, n=1;
    for( cont; cont <= 10;)
    {
        if(n % 2==0)
           {
            printf("- %d", n);
            cont++;
           }
        n++;
    }

}

Saida.:

2 - 4 - 6 - 8 -10 -12...

Isso pode aumentar conforme alterar o for(cont; cont <= 100;)

Vai mostrar os 100 divisores.

Espero ter ajudado e ate...

 

Obs.: Sobre os meus codegos: eu não sei como deixar bonitinho como uns dizem: vai no cadeado acima e insere lá. Eu já fiz e fica feio e por isso deixo dessa forma.

Uso o cel Android e compilo no App Cxxdroid sem problema.

Mais dúvida post...

Luís.