Fatoração em C [ resolvido]

Leite Estragado disse:

Do jeito que ele está, entra num loop infinito, da o resultado só que ele continua dividindo toda vida. Se eu mudo o While para n > 1, resolve o problema.
Mas aí que tá, nao era pra funcionar com n > 0?
já que ( usando o exemplo, depois da ultima divisão ):
n = 1
1 / 7 = 0
logo n = 0, e nisso esse saí-se do laço?

#include <stdio.h>

/* Recebe um número inteiro n > 0 e mostra sua decomposição em

fatores primos, calculando a multiplicidade de cada fator */

int main(void)

{

       int n, p, q, primo, div;

       printf("Informe n: &quot;

       scanf("%d", &n);

       p = 2;

       while (n > 1) {

             q = 0;

                while (n % p == 0) {

                q = q + 1;

                        n = n / p;

             }

              if (q > 0)

              printf("fator %d com multiplicidade %d\n", p, q);

              primo = 0;

              while (! primo) {

                       p = p + 1;

                       div = 2;

                      primo = 1;

                  while (div <= p / 2 && primo) {

                       if (p % div == 0)

                            primo = 0

                       else

                            div = div + 1;

                 }

         }

     }

   return 0;

}

tpcvasco disse:

Certo, mas pode ficar tranquilo q no fundo esse código é quase a mesma coisa q vc fez, só q de uma maneira diferente (lembre-se sempre q, na computação, haverá sempre infinitas maneiras diferentes de implementar o mesmo algoritmo).
A única coisa q ele fez de diferente foi testar se um número é primo com divisores só até a metade do valor do número. Existe uma maneira (q não lembro qual é rsrs) q define isso.

Mas se vc quiser tirar uma onda na sua turma, na próxima aula vc pode mardar pro seu professor q ainda existe uma maneira de melhorar esse algoritmo. É só vc lembrar q, com exceção do 2, nenhum outro número par é primo. Então, vc pode incrementar p de 2 em 2, não apenas de 1 em 1, e testar só os números ímpares.

Felipe Fontes disse:

Sem falar que não precisa testar até a metade do numero, basta até a raiz quadrada do numero.

#include <stdio.h>

#include <math.h>



int main(void) {

    int i;

    int n;

    int primo;

    int aux;

    int tmp;

    

    primo = 1;

    i = 1;

    printf("Digite n: &quot;

    scanf("%d", &n);

    

    aux = 0 ;

    

    while ( n > 1 ) {

    tmp = 2;

    i = 0;

    primo++;

       /* nesse while ele pega o proximo n primo, aqui passa normal */

        while ( tmp <= sqrt(primo))

        {

            if ( primo % tmp == 0 )

            {

                primo++;

                tmp = 2;

            }

            tmp++;

        }

        

        while ( n % primo == 0 )

        {

            i++;

            n = n / primo;

        }

        if (i)

            printf("Fator %d multiplicidade %d \n", primo, i);

    }

    

    return 0;

}