Resolução de problemas: Problemas de baixa complexidade: Numéricos: Count the factors

De Wikibooks

[editar] Conte os fatores

[editar] O Problema

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

60 = 2 * 2 * 3 * 5

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.

[editar] A Solução

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[])
{
	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