Mostrar código-fonte de Resolução de problemas/Count the factors

== Conte os fatores ==
=== O Problema ===

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

<center><math>60 = 2*2*3*5</math></center>

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 ===

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

<center>
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
</center>

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'''.

<center>
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
</center>

Depois para o '''três''':

<center>
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
</center>

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

<center>
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'''
</center>

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

<center>
'''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'''
</center>

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

Uma implementação possível para o '''{{Busca|crivo de Eratóstenes}}''':
<syntaxhighlight lang="cpp">
 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';
 		}
 }
</syntaxhighlight>

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.<br>
Assim temos:
<syntaxhighlight lang="cpp">
 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];
 }
</syntaxhighlight>

Em que '''n''' é o '''número''' em questão, '''c''' o '''contador''' e '''pri''' o vetor de '''primos'''.
<br>
----
Veja esse problema em: http://acm.uva.es/p/v106/10699.html

{{AutoCat}}