Algorithm Factorization in C

Question

I need to create a program in C, which factors in any number the user enters. I wrote this code, but it doesn’t work completely because it only calculates once. I don’t want an answer ready, I want an explanation, why that happens.

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

int main()
{
    int num, i, j, cont=0, resp;

    printf("digite um numero inteiro positivo:\n");
    scanf("%i", &num);

    for(i=1;i<10000;i++)
    {
        for(j=1;j<10000;j++)
        {
            if(i%j==0)
                cont++;
            if(cont==2)
            {
                resp=num/i;
                printf("%i |%i=%i", num, i, resp);
            }
        }

        if(resp==1)
            break;
    }

    return 0;
}

Answer 1

The if(cont==2) has to be outside the for(j=1;j<10000;j++), or he will divide by i whenever he finds his second divider.

For example: let’s say my i is 4, when j = 2, cont = 2, soon it will make the division.

In addition, every time you do not go outside, it is necessary to reset the container, otherwise it will only do the division a reduced number of times.

Answer 2

    #include <stdio.h>


int primo(int k);

int proxPrimo(int k);

main()
{
    int j, g;
    int numero, i;
    printf("Digite um numero: ");
    scanf("%d", &numero);
    int fatores[numero], k = 0;
    g = numero;
    printf("\n\n\n\n");

    for(i = 2; numero != 1; i = proxPrimo(i)){
        if(numero % i == 0){
            while(numero % i == 0){
                fatores[k] = i;
                numero /= i;
                k++;
            }
        }else{
            continue;
        }
    }

    printf("-----------------------------------------------------------------\n");
    printf("Fatoracao de %d\n", g);
    printf("-----------------------------------------------------------------\n\n");

    for(j = 0; j < k; j++){
        if(j == 0){
            printf("%d * ", fatores[j]);
        }else if(j == k-1){
            printf(" %d.", fatores[j]);
        }else{
            printf(" %d * ", fatores[j]);
        }
    }
    if(primo(g) != 0){
        printf("\n\n-----------------------------------------------------------------\n\n");
    }else{
        printf("\t[PRIMO]\n\n----------------------------------------------------------\n\n");
    }

    return 0;
}

primo(int k)
{
    int div = 0, i = k;

    for(i = 1; i <= k; i++){
        if(k % i == 0){
            div++;
        }
    }

    if(div == 2){
        return 0;
    }else{
        return 1;
    }
}

proxPrimo(int k)
{
    if(primo(k) == 0){
        k++;
    }

    while(primo(k) != 0){
        k++;
    }

    return k;
}

Answer 3

I would use a different method than yours, I think more unlimited, see if you agree with me:

#include <iostream>
#include <conio.h>

using namespace std;

int main()
{
    int num=0 , cont=0 , i=2 ;

    cout << "Digite um numero para fatora-lo" << endl;
    cin  >> num ;


        for ( i=num-1 ; i > 1 ; i--)
        {
            if (num%i == 0) // Se o resto da divisao for 5 ele armazena no contador
            {
                cont++; // contador recebe +1
                cout << "O numero foi dividido por " << i << " , " << cont << " vezes" << endl;
                num = num/i; // numero se torna o numero depois da divisao
            }
            else
            {
                cout << "O numero " << i << " Nao e usado para essa fatoracao " << endl; // caso o numero nao seje utilizado

            }
            cont = 0;
        }


    return 0;
}

I posted this because I couldn’t find a viable solution with the answers here, have a good night ^^

Answer 4

Usually when we talk about factoring a number what we want are the prime factors and their multiplicity. Here’s a factorization algorithm I made based on the Eratosthenes sieve.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define tamanho_crivo 10000

int main()
{
    int num, i, j, cont=0, resp, fatores[1000], vezes[1000], aux;

    // Monta o vetor para determinar se um número é primo ou não
    char crivo[tamanho_crivo];
    memset(crivo, 1, tamanho_crivo);
    crivo[0] = 0;
    crivo[1] = 0;
    for(i=2; i < tamanho_crivo; i++){
        if(crivo[i] == 1)
            for(j=2*i; j < tamanho_crivo; j = j+i)
                crivo[j] = 0;  // Números que não são primos, pois são divisíveis por i 
    }

    printf("digite um numero inteiro positivo:\n");
    scanf("%i", &num);

    // Parte que executa a fatoração
    memset(vezes, 0, 1000*sizeof(int));
    aux = num;
    for(i=2; i<num; i++){
        if(crivo[i]){
            if(aux%i == 0){
                fatores[cont] = i;
                cont++;
            }
            while(aux%i == 0){
                vezes[cont-1]++;
                aux = aux/i;
            }
        }
    }

    // Imprime os resultados
    printf(" ");
    for(i=0; i< cont; i++)
            printf("%d    ", vezes[i]);
    printf("\n");
    for(i=0; i< cont; i++){
        printf("%d", fatores[i]);
        if(i!=cont-1)
            printf("  * ", fatores[i]);
    }

    return 0;
}