Crivo de Eratóstenes

Os números primos possuem várias aplicações, como criptografia e segurança dos dados (por exemplo: SSL, X509, certificados, chaves privadas, ..), e a obtenção deles de forma eficiente sempre foi alvo de estudo dos matemáticos.

O Crivo de Eratóstenes é um algoritmo muito simples e eficiente para gerar números primos. Esse algoritmo consiste em remover os múltiplos de um determinando conjunto.
Por exemplo, quero achar todos os números primos de 1 a 120. O algoritmo gera um conjunto com todos os números de 2 a 120 (já que 1 não é primo). Utiliza o primeiro número (que no caso é 2), e vai removendo os múltiplos: 4, 6, 8, 10, .... e marca o 2 como primo, procura o próximo não removido que é o 3, marca como primo, e vai removendo os múltiplos se não foram removidos anteriormente: 6, 9, 12, 15... Ele vai fazendo isso até raiz quadrada do número máximo que você quer verificar. Se a raiz não é inteira, truncamos (menor inteiro). No nosso exemplo, raiz quadrado de 120, que fica entre 10 e 11 e portanto só precisamos verificar os múltiplos até 10. Garantindo que buscamos por todos os múltiplos possíveis até 120.

O funcionamento pode ser visto através dessa animação encontrada no artigo do Crivo de Eratóstenes do Wikipedia:

Uma melhoria possível é ao invés de iniciar do número 2, iniciar do número 3 e ir pulando um elemento (incremento de 2), ao invés de sempre pegar o próximo multiplo. Dessa forma já eliminamos todos os pares (que não são primos), exceto o 2. Segue a implementação utilizando Java com o código comentado.

package br.com.thiagovespa.prime.utils;

import java.util.LinkedHashSet;
import java.util.Set;

public class SieveOfEratosthenes {

	public Set<Integer> sieve(int max) {
		Set<Integer> result = new LinkedHashSet<Integer>();
		if (max > 1) {
			result.add(2);
		}

		// Lista dos possíveis primos
		boolean[] isNotPrime = new boolean[max + 1];

		// Busca por todos os elementos até a raiz quadrado do máximo e
		// incrementa de dois em dois já que os pares não são primos
		for (int elem = 3; elem <= Math.sqrt(max); elem += 2) {
			// Se ainda não eliminei da lista
			if (!isNotPrime[elem]) {
				// Pego o próximo multiplo
				int multiple = elem + elem;
				while (multiple <= max) {
					// Se é multiplo, não é primo
					isNotPrime[multiple] = true;
					// Pego o próximo multiplo
					multiple += elem;
				}
			}
		}

		// Preencho a lista com todos os primos
		for (int position = 3; position <= max; position += 2) {
			if (!isNotPrime[position]) {
				result.add(position);
			}
		}

		return result;
	}

	public static void main(String[] args) {
		SieveOfEratosthenes sieve = new SieveOfEratosthenes();
		int valorMaximo = 120;
		System.out.println("Realizando busca para números até: " + valorMaximo);
		Set<Integer> primes = sieve.sieve(valorMaximo);
		System.out
				.println("Encontrados: " + primes.size() + " números primos.");
		for (Integer prime : primes) {
			System.out.println(prime);
		}
	}

}

Existe algumas melhorias que podem ser feitas. Além da possibilidade de paralelizar o código. Nessa versão ele não consegue obter números primos maiores que 32 bits, por causa da limitação do int e perco 3 bits do array de candidatos para evitar cálculos desnecessários na execução. Em breve colocarei um post com o Crivo de Aktin, que é uma versão mais rápida para números primos maiores. A idéia é implementar um Crivo de Aktin para ser executado concorrentemente (com uso de Threads) e para números primos bem grandes.

Share on Facebook

Tweet

Follow us