Resolução de problemas/Count the factors
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