Resolução de problemas/Count the factors

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa

Conte os fatores[editar | editar código-fonte]

O Problema[editar | editar código-fonte]

Imagine que você precisa encontrar os diferentes fatores primos de um número natural. Por exemplo:

O número 60 pode ser formado pelo produto de três números primos distintos. No entanto 60 é um número muito pequeno e nós precisamos computar números grandes como 1000000 no máximo. Portanto não podemos usar qualquer algoritmo para achar os números primos e testar quais deles são fatores do número natural em questão.

A Solução[editar | editar código-fonte]

Um algoritmo possível para solucionar o problema usa o crivo de Eratóstenes.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

O algoritmo trabalha da seguinte maneira, ele seleciona cada elemento e marca seus múltiplos como não primos, note que não precisamos mais procurar pelos múltiplos de um número que já foi marcado como não primo. Por exemplo para o 2, no exemplo acima, marcariamos todos os números pares como não primos.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Depois para o três:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

O quatro já foi marcado, vamos para o cinco:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

E assim por diante, assumimos que o número 1 não é primo:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Assim temos todos o números primos menores que 25.

Uma implementação possível para o crivo de Eratóstenes:

 void crivo(int primos[])<br>
 {
 	char crivo[MAX];
 	int i, j, k = 0;
 
 	for (i = 0; i < MAX; i++)
 		crivo[i] = '1';
 	crivo[0] = crivo[1] = '0';
 	for (i = 2; i < MAX; i++)
 		if (crivo[i] == '1')
 		{
 			primos[k++] = i;
 			for (j = 2 * i; j < MAX; j += i)
 				crivo[j] = '0';
 		}
 }

No final do algoritmo acima teremos todos os primos menores que MAX no vetor primos. Depois disso é só testar quais primos são fatores do número em questão e contar sempre que encontrarmos um fator diferente.
Assim temos:

 int aux = n, c = 0;
 
 for (i = 0; pri[i] <= n; ++i)
 {
 	if (aux % pri[i] == 0)
 		++c;
 	while((aux % pri[i]) == 0)
 		aux /= pri[i];
 }

Em que n é o número em questão, c o contador e pri o vetor de primos.


Veja esse problema em: http://acm.uva.es/p/v106/10699.html