Este é o código do Andre para encontrar primos e que depois foi melhorado pelo SnowRaptor.
Esse método funciona bem para intervalos pequenos.
Para intervalos maiores, esse é bem mais rápido (mas mais memória). Em C:
// Defina o limite que quiser, eu usei um milhao
#include <stdio.h>
#define MAXIMO 1000000
int main(int argc, char* argv[]) {
short nums[MAXIMO];
int i, j;
for( i = 0; i < MAXIMO; i++ )
nums[i] = 1;
// Colocamos 0 em todos os numeros que forem multiplo de alguma coisa
for( i = 2; i < MAXIMO; i++ ) {
if(nums[i]) {
for( j = i*2; j < MAXIMO; j += i) {
nums[j] = 0;
}
}
}
// Onde o array tiver valor 1, aquele numero eh primo
for( i = 2; i < MILLION; i++ ) {
if(nums[i]) {
printf("%d\n",i);
}
}
return 0;
}
Edit: Esse algoritmo não é meu, só 'peguei emprestado' e o passei para C. A fonte é essa.
Bom, irei colocando uns códigos aqui que, quem sabe, talvez possam ser úteis a mais alguém.
É uma tentativa inicial modesta - e provavelmente infrutífera - de estimular outras pessoas a participarem do fórum.
Nesse caso específico pessoas que se interessem por códigos.
Também fiz uma classe para resolver este problema de achar primos. Ao contrário do código em Phyton do Dante (que não é esse aí em cima, é um anterior), o meu monta uma estrutura de dados (uma lista) com todos os primos existentes em um intervalo qualquer [2, n]. Onde n é um inteiro qualquer de 32 bits.
Esta lista pode ser usada para encontrar todos os fatores primos de um inteiro qualquer de 64 bits. E quase instantaneamente. Ou seja, todos os fatores primos de número no intervalo entre 0 e 8 quinquilhões, ou oito milhões de trilhões. (Para isso fiz outro código)
Meu código, a exemplo do código em C listado acima, também se baseia no crivo de Eratóstenes.
O crivo começa com uma lista de todos os números de 2 a N e retira inicialmente desta lista todos os múltiplos de 2. O próximo inteiro que ainda não foi excluído é primo, então retira-se todos os múltiplos deste primo. E assim sucessivamente até raiz quadrada de N, quando todos os não primos terão sido excluídos da lista e só restarão os primos.
Não é necessário prosseguir além de raiz de N porque se N não tiver um divisor Q menor ou igual a sua raiz, então também não tem divisor D maior ou igual que sua raiz e é primo. Já que se N/D = Q implica que N/Q = D.
Logo,
E se isso é verdade para N então é verdade também para qualquer inteiro menor que N. Então qualquer número menor que N tem divisor menor que raiz de N ou é primo.
Mas eu fiz algumas modificações para torna-lo mais eficiente. Basicamente utilizei ideias simples:
(a) Como observou Andre o crivo necessita de muita memória, o que limitaria a extensão do intervalo. Então a ideia dessa classe é gerar uma lista de primos que possa ser estendida.
No método appendList() é detectado se a máquina tem memória suficiente para montar uma lista com todos os primos até
Ni. Se não, pode ser escolhido um
Nj menor e depois de criada a lista ela pode ser estendida para incluir os primos de algum intervalo ainda maior. Assim sucessivamente, adaptando-se à memória disponível, até termos uma lista de
todos os primos entre 2 e
Ni.
A saída abaixo é um exemplo implementado no main() da classe. O programa tenta encontrar todos os primos até 200 milhões mas não há memória. Então tenta o intervalo até 100 milhões mas ainda não há memória. Tenta até 50 milhões e tem sucesso.
Em seguida a lista é estendida para todos os primos até 90 milhões.
Sem memória para obter primos até 200000000
Sem memória para obter primos até 100000000
10.000º número primo = 104729
3001134 primes in [2, 50000000] : 49999991 is the last prime on list.
5216954 primes in [2, 90000000] : 89999999 is the last prime on list.
BUILD SUCCESSFUL (total time: 33 seconds)Isto é possível porque a classe em vez de montar o array inicial representando o intervalo a ser pesquisado, ela pode trabalhar com pedaços deste array. Ou seja, subintervalos e encontrar todos os primos neste subintervalo. Em seguida desalocar a memória deste array e alocar outro para pesquisar um novo subintervalo consecutivo ao anterior. E assim sucessivamente.
(b) Mas este array não precisa ter N posições como no código acima. Sabemos que 2 é o único par primo, portanto basta mapear ímpares no array. Buscamos apenas primos ímpares e isso já economiza metade da memória e do tempo de processamento.
(c) Um problema no código em C é que depois de excluídos todos os não primos do array, é preciso percorrer todo o array para listar os primos. Isto pode ser evitado se simularmos uma lista duplamente ligada nesse array. Então a retirada de um não primo, em vez de ser implementada marcando-se esta posição no array, passa a ser simplesmente excluir um nó da lista. E quando o algoritmo termina a lista já está pronta sem necessidade de percorrer o array novamente.
(d) E veja essa linha do código em C:
for( i = 2; i < MAXIMO; i++ )Se o array for como uma lista duplamente ligada não há mais necessidade de percorre-lo todo, usando incrementos de uma unidade. O loop pula direto para o próximo primo no intervalo e começa a excluir seus múltiplos.
(e) No loop interno, aninhado com este mostrado acima, há duas coisinhas que podem melhorar bastante:
Em vez de
for( j = i*2; j < MAXIMO; j += i)1 - Não precisa ter incremento i. Pode ser i * 2. Com incremento i, o j está assumindo, alternadamente, valores ímpares e pares. Mas sabemos que pares não são primos e por isso não estão mapeados no array. Então podemos salta-los.
2 - Outro pulo do gato é que j não precisa iniciar em i * 2, mas sim em i². Assim se queremos excluir todos os múltiplos de de 53, não é preciso começar pelo 106. Pode iniciar em 2809 porque todos os múltiplos de 53 abaixo de 2809 já teriam sido excluídos como múltiplos de primos menores que 53.
(Pense em porque este algoritmo pode parar em raiz de N, e vai entender porque pode iniciar a busca por múltiplos a partir do quadrado do número primo.)
Juntando todas estas ideias temos o código da classe:
package br.com.hkp.classes.math.numberstheory;
import java.util.LinkedList;
import java.util.ListIterator;
/**
* Esta classe obtem uma lista com todos os numeros primos ateh o valor maximo
* <b>n</b> passado como argumento para o construtor da classe.
* <p>
* A lista criada na chamada do construtor pode ser estendida pelo metodo
* {@link #appendList(int) }. Exemplo: Se o construtor foi chamado com
* argumento igual 100 entao inicialmente eh gerada uma lista com todos os
* primos entre 2 e 100. Mas se quisermos estender esta lista para todos os
* primos entre 2 e 199 basta executar appendList(99). E se em seguida for
* executado appendList(21) a lista passarah a conter todos os primos entre 2 e
* 220.
* <p>
* Ou seja, appendList(n) estende o intervalo de inteiros [2, F] de onde foi
* extraida a lista com todos os primos deste intervalo, para o intervalo
* [2, F + n]. E entao {@link #getList() } retornara uma lista com todos os
* primos entre 2 e F + n.
*
* @author "Pedro Reis"
* @since 1.0
*/
public class ExtensibleSieve
{
/*
A classe implementa um algoritmo baseado no crivo de Eratostenes
e, para isso, cria um array com os inteiros do intervalo de onde serao
extraidos os numeros primos. O metodo implementa uma lista duplamente ligada
sobre este array e para facilitar a leitura do codigo sao definidas aqui
algumas constantes uteis na manipulacao desta lista.
*/
/*
Indica a posicao anterior (previa) que esta sendo apontada pelo noh corrente
Pois cada elemento do array <numbers> e um ponteiro para um array de tamanho
2, onde a posicao 0 (PREV) aponta para o no anterior. E a posicao 1 para o
proximo noh da lista duplamente ligada.
*/
private static final int PREV = 0;
/*Indica que a posicao 1 do array aponta para o proximo noh da lista
duplamente ligada implementada sobre o array <int numbers[][]>
*/
private static final int NEXT = 1;
/*
Indica que um ponteiro nas posicoes PREV ou NEXT do array numbers [][]
aponta para NULL
*/
private static final int NULL = -1;
/*
Se um noh eh removido da lista seu ponteiro PREV recebe o valor da constante
REMOVED, indicando que nao estah mais na lista.
*/
private static final int REMOVED = -2;
/*
O primeiro numero (sempre impar) mapeado no array numbers[][]
*/
private int firstNumber;
/*
O limite superior do intervalo de onde eh extraida a lista de primos.
*/
private int lastNumber;
/*
A raiz quadrada de lastNumber
*/
private int sqrtOfLastNumber;
/*
Aponta para o indice do primeiro elemento da lista criada no array
numbers[][]. Inicialmente este indice eh 0, mas se o elemento na primeira
posicao for retirado por ser nao primo, entao pointerToList ira apontar
para o sucessor deste numero. E, novamente, se este for retirado da lista
entao pointerToList apontarah para o seu sucessor. De modo que pointerToList
sempre aponta para o primeiro noh da lista implementada sobre o array
numbers[][] que eh declarado e criado no metodo appendList(int)
*/
private int pointerToList;
/*
Uma lista ligada que contem todos os numeros primos de um determinado
intervalo de inteiros que se inicia em 2. (O primeiro primo da lista)
*/
private final LinkedList <Integer> list;
/**
* Construtor da classe. O objeto criado por este construtor irah construir
* uma lista com todos os primos no intervalo de 2 ateh n.
*
* @param n {@link #getList() } retornarah uma lista com todos os primos de
* 2 ateh <b>n</b>
*
* @throws IllegalArgumentException Excecao lancada se n menor que 2.
*
* @throws OutOfMemoryError Lancada se nao houver memoria suficiente para
* gerar a lista de primos. Nesse caso deve-se tentar criar o objeto com
* um valor menor para n.
*/
/*[01]----------------------------------------------------------------------
* Construtor da classe
--------------------------------------------------------------------------*/
public ExtensibleSieve(int n)
throws IllegalArgumentException, OutOfMemoryError
{
if (n < 2) throw new
IllegalArgumentException("Impossível criar lista.");
/*
Cria a lista e adiciona o primeiro primo.
*/
list = new LinkedList<Integer>();
list.add(2);
/*
Se n maior que 2 chama appendList() para adicionar mais primos na lista.
*/
if (n > 2) appendList(n);
}//fim de ExtensibleSieve()
/*[02]----------------------------------------------------------------------
* Retorna o numero referente a uma posicao no array de inteiros
--------------------------------------------------------------------------*/
private int getNumber(int index)
{
return (2 * index) + firstNumber;
}//fim de getNumber()
/*[03]----------------------------------------------------------------------
* Retorna a posicao no array de inteiros referente a um numero
--------------------------------------------------------------------------*/
private int getIndex(int number)
{
return (number - firstNumber) / 2;
}//fim de getIndex()
/*[04]----------------------------------------------------------------------
* Retira os nao primos de uma lista de n inteiros e acrescenta os primos
* neste intervalo a lista de primos.
--------------------------------------------------------------------------*/
private void getPrimes(int [][] numbers)
throws OutOfMemoryError
{
int index = pointerToList;
/*
Retira todos os multiplos dos numeros primos que constarem no array
numbers[][]. O loop se encerra quando atingir raiz quadrada de
lastNumber.
*/
while (numbers[index][NEXT] != NULL)
{
/*
Obtem o inteiro primo referente a posicao index da lista.
*/
int number = getNumber(index);
/*
Se number for maior que a raiz quadrada de lastNumber entao todos
os nao primos jah foram retirados da lista e o loop se encerra.
*/
if (number > sqrtOfLastNumber) break;
int step = 2 * number;
/*
A busca por multiplos do primo number que serao retirados da lista
pode iniciar em N = number^2. Pois todos os nao primos menores que
number^2 jah terao sido retirados da lista.
*/
int first = number * number;
removeMultiples(first, step, numbers);
/*
Pula para o proximo primo da lista.
*/
index = numbers[index][NEXT] ;
}//fim do while
/*
Ao fim do loop while acima soh restarao primos nao marcados como
REMOVED no array numbers[][]. O loop abaixo percorre todos estes nohs
e adiciona os valores primos a uma LinkedList
*/
index = pointerToList;
while (index != NULL)
{
list.add(getNumber(index));
index = numbers[index][NEXT];
}
}//fim de getPrimes()
/**
* O construtor desta classe gera uma lista com todos os primos no intervalo
* de 2 ateh n. Onde n eh o argumento passado ao construtor. Este metodo
* permite estender este intervalo.
*
* @param n Em quantos inteiros o intervalo de onde eh obtida a lista de
* primos eh alargado.
* @throws OutOfMemoryError Se nao houver memoria suficiente para gerar a
* lista esta excecao eh lancada.
*/
/*[05]----------------------------------------------------------------------
* Estende a lista com os numeros primos
--------------------------------------------------------------------------*/
public void appendList(int n)
throws OutOfMemoryError
{
if (n < 1) return;
boolean creatingNewList = (list.size() == 1);
/*
Se appendList() foi chamado pelo construtor list.size() == 1.
*/
if (creatingNewList)
{
firstNumber = 3;
lastNumber = n;
}
else //senao a lista jah foi criada e serah estendida por appendList()
{
firstNumber = lastNumber + 1 + (lastNumber % 2);
/*
Estende o intervalo de onde sao extraidos os primos em mais n
inteiros.
*/
lastNumber += n;
if (firstNumber > lastNumber) return;
}//fim do if else
sqrtOfLastNumber = (int)Math.sqrt(lastNumber);
/*
Calcula o tamanho do array para conter apenas os inteiros impares do
intervalo
*/
int length =
(lastNumber - firstNumber + 1 + (lastNumber % 2)) /2;
int[][] numbers = new int[length][2];
/*
Monta uma lista duplamente ligada sobre o array numbers.
*/
pointerToList = 0;
for (int i = 0; i < numbers.length; i++)
{
numbers[i][PREV] = i - 1;
numbers[i][NEXT] = i + 1;
}
numbers[0][PREV] = NULL;
numbers[numbers.length - 1][NEXT] = NULL;
/*
Estende a lista atual se appendList() nao estiver sendo chamado pelo
construtor da classe.
*/
if (! creatingNewList )
{
ListIterator<Integer> it = list.listIterator(1);
while ( it.hasNext() )
{
int prime = it.next();
/*
Se prime for maior que a raiz quadrada de lastNumber entao todos
os nao primos jah foram retirados da lista e o loop se encerra.
*/
if (prime > sqrtOfLastNumber) break;
*/
int firstMultiple = getNumber(pointerToList);
int q = firstMultiple / prime;
if ( (q * prime ) < firstMultiple )
firstMultiple = q * prime + prime;
if ((firstMultiple % 2) == 0) firstMultiple += prime;
int primePower2 = prime * prime;
if (firstMultiple < primePower2) firstMultiple = primePower2;
/*
Remove todos os multiplos deste primo do array numbers[][]
*/
removeMultiples(firstMultiple, 2 * prime, numbers);
}//fim do while
}//fim do if
getPrimes(numbers);
}//fim de appendList()
/*[06]----------------------------------------------------------------------
* Remove todos os multiplos de um determinado primo cujo primeiro multiplo
* na lista eh indicado pelo argumento first.
--------------------------------------------------------------------------*/
private void removeMultiples(int first, int step, int[][] numbers)
{
int removingIndex = getIndex(first);
/*
Retira todos os multiplos do primo que ainda constarem na lista.
*/
for (int i = first; removingIndex < numbers.length; i += step)
{
/*
Se jah foi retirado numbers[removingIndex][PREV] estah marcado
como REMOVED
*/
if (numbers[removingIndex][PREV] != REMOVED)
{
/*
Faz o no anterior apontar para o posterior e o no posterior
apontar para o anterior, retirando assim o no apontado por
removingIndex da lista.
*/
int prevNode = numbers[removingIndex][PREV];
int nextNode = numbers[removingIndex][NEXT];
numbers[removingIndex][PREV] = REMOVED;
if (prevNode != NULL)
numbers[prevNode][NEXT] = nextNode;
else
pointerToList = nextNode;
if (nextNode != NULL) numbers[nextNode][PREV] = prevNode;
}
/*
Visita o proximo multiplo de number que pode ainda nao estar
marcado como REMOVED
*/
removingIndex = getIndex(i);
}//fim do for i
}//fim de removeMultiples()
/**
* Retorna uma lista de Integers com todos os primos no intervado de 2 ateh
* <b>n</b>
*
* @return Uma lista ligada com todos os primos do intervalo. Esta lista
* deve ser apenas para leitura, seus elementos não devem ser modificados.
* Pois se a lista for alterada ela será passada com essa alteração na
* próxima vez em que este método for executado.
*/
/*[07]----------------------------------------------------------------------
* Retorna a lista com os numeros primos
--------------------------------------------------------------------------*/
public LinkedList<Integer> getList()
{
return list;
}//fim de getList()
/**
* Retorna o maior numero do intervalo.
*
* @return O limite superior do intervalo de inteiro de onde foi extraida
* a lista com todos os primos.
*/
/*[08]----------------------------------------------------------------------
* Retorna o limite superior do intervalo de onde foi obtida a lista de
* primos
--------------------------------------------------------------------------*/
public int lastNumber()
{
return lastNumber;
}//fim de lastNumber()
/**
* Retorna o maior primo da lista.
*
* @return O maior numero primo da lista.
*/
/*[09]----------------------------------------------------------------------
* Retorna o maior numero primo na lista
--------------------------------------------------------------------------*/
public int lastPrime()
{
return list.get(list.size() - 1);
}//fim de lastPrime()
/**
* O numero de primos na lista.
*
* @return Retorna quantos primos ha na lista.
*/
/*[10]----------------------------------------------------------------------
* Retorna quantos primos ha na lista
--------------------------------------------------------------------------*/
public int howManyPrimesOnList()
{
return list.size();
}//fim de lastPrime()
/**
* Uma representacao textual do objeto.
*
* @return Quantos primos ha na lista, o intervalo de inteiros de onde foram
* extraidos os primos da lista e o maior numero primo na lista.
*/
/*[11]----------------------------------------------------------------------
* Informacao textual sobre o objeto
--------------------------------------------------------------------------*/
@Override
public String toString()
{
return "" + howManyPrimesOnList() +
" primes in [2, " + lastNumber() + "] : " +
lastPrime() + " is the last prime on list.";
}//fim de toString()
/**
* Um metodo exemplificando usos da classe.
*
* @param args Argumentos de linha de comando. Nao utilizados.
*/
public static void main(String[] args)
{
int value = 200000000;
boolean trying = true;
ExtensibleSieve sv = null;
while (trying)
{
try
{
sv = new ExtensibleSieve(value);
if (sv.getList().size() >= 10000)
System.out.println
("10.000º número primo = "+ sv.getList().get(9999));
else
System.out.println(sv.getList());
System.out.println(sv);
trying = false;
}
catch (OutOfMemoryError e)
{
System.out.println("Sem memória para obter primos até " +value);
value /= 2;
}
catch (IllegalArgumentException e)
{
System.out.println(e);
trying = false;
}
}//fim do while
sv.appendList(40000000);
System.out.println(sv);
}//fim de main()
}//fim da classe ExtensibleSieve
