Ir ao conteúdo
  • Cadastre-se
diogo moura

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

Recommended Posts

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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++;

  }

}

 

Compartilhar este post


Link para o post
Compartilhar em outros sites
#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;
}

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

@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

Compartilhar este post


Link para o post
Compartilhar em outros sites

@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.

Compartilhar este post


Link para o post
Compartilhar em outros sites

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.

Compartilhar este post


Link para o post
Compartilhar em outros sites
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.

Compartilhar este post


Link para o post
Compartilhar em outros sites
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.

Compartilhar este post


Link para o post
Compartilhar em outros sites
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.

Compartilhar este post


Link para o post
Compartilhar em outros sites

@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) ).

Compartilhar este post


Link para o post
Compartilhar em outros sites

@isrnick Exemplo?

Compartilhar este post


Link para o post
Compartilhar em outros sites
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

 

 

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

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".

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites
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.

Compartilhar este post


Link para o post
Compartilhar em outros sites
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 .  

Compartilhar este post


Link para o post
Compartilhar em outros sites

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.

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×