Programa em C++

[gabriel.carvalho 0]

Crie um programa que decomponha um número em seus fatores primos.

 

 

quociente

|

|

630|2 -- divisores primos

315|3

105|3

35 |5

7 |7

1 |

 

Comece com o número primo 2 e vá aumentando a medida que o número é decomposto. Se ele não for divisível pelo próximo primo, busque um primo maior.

 

 

 

Para o exemplo dado, a resposta tem que ser:

 

630 = 2 x 3 x 3 x 5 x 7

 

Para obter uma sequência de números primos, utilize o “Crivo de Eratóstenes”:

 

 

Crie uma lista de inteiros consecutivos, de dois até “n” (o limite).

 

1.Inicialmente, faça a variável “p” igual a 2, o primeiro número primo;

 

2.Retire da lista todos os múltiplos de “p”, menores ou iguais a “n” (o limite). Por exemplo: 2*p, 3*p, 4*p,...

 

3.Encontre o primeiro número restante na lista maior que “p” (é o próximo primo); Substitua o valor de “p” por esse número;

 

4.Repita os passos 3 e 4 até que o quadrado de “p” seja maior que “n” (p2 > n);

 

5.Ao final, todos os números restantes na lista são primos;

 

 

 

Uma dica: “n” é o próprio número que se deseja fatorar. Crie uma lista encadeada (std::list) e vá retirando “list.erase()” até restarem apenas os primos de 2 até o número. Use esta lista para encontrar os primos necessários à fatoração.

[quitZAUMMM 18]

hum.. e?