C-Factor Algorithm

Posted on

Question :

I need to create a program in C that fills any number that the user types. I wrote this code, but it does not work fully because it calculates only once. I do not want a ready answer, 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;
}
``````

The `if(cont==2)` has to be outside the `for(j=1;j<10000;j++)` , otherwise it will divide by i whenever you find the second divisor of it.

For example: let’s say my i is 4, when j = 2, cont = 2, then it will split.

In addition, with each turn you give in the outermost, you must zero the cont, otherwise it will only do the division a few times.

I would use a different method than yours, I find it 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
{
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 post this because I could not find a workable solution with the answers here, have a good night ^^

Generally speaking when factoring a number, what you want is the prime factors and their multiplicity. There goes a factorization algorithm that I did based on the Eratosthenes screen.

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

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;
}
``````

``````    #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("nnnn");

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 %dn", g);
printf("-----------------------------------------------------------------nn");

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("nn-----------------------------------------------------------------nn");
}else{
printf("t[PRIMO]nn----------------------------------------------------------nn");
}

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;
}
``````