Primeiramente vamos fazer da maneira mais simples possível, que é para cada número calcular todos os primos que o antecedem:
public static void testePrimoCalcularUmPorUm() { String pathIn = "/home/pognao/testePrimoCalcularUmPorUm"; BufferedWriter wr = null; try { wr = new BufferedWriter(new FileWriter(pathIn)); for (int numero = 2; numero < PAR_TESTE; numero++) { /* * como verificar se um numero é primo ? Um número primo só pode * ser divisível por 1 e por ele mesmo. */ ArrayList<Integer> numerosPrimos = new ArrayList<>(); numerosPrimos.add(1); for (int i = 2; i < numero; i++) { if (ehPrimo(i)) { numerosPrimos.add(i); wr.write(i); } } } wr.close(); } catch (Exception e) { } }
Agora a forma melhorada consistem em armazenar todos os primos até o teto definido em um array e depois apenas ir buscando neste array os resultados.
public static void testePrimoCalcularArray() { ArrayList<Integer> numerosPrimos = new ArrayList<>(); numerosPrimos.add(1); for (int i = 2; i < PAR_TESTE; i++) { if (ehPrimo(i)) { numerosPrimos.add(i); } } String pathIn = "/home/pognao/testePrimoCalcularArray"; BufferedWriter wr = null; try { wr = new BufferedWriter(new FileWriter(pathIn)); for (int numero = 2; numero < PAR_TESTE; numero++) { for (Integer imprimir : numerosPrimos) { if (imprimir < numero) { wr.write(imprimir); } else break; } } wr.close(); } catch (Exception e) { } }
Resultados
Para realizar os testes foram utilizados 3 parâmetros, o primeiro é calcular a lista de primos até o número 100, o segundo até o 1000 e o terceiro até 10000.
O resultado é mostrado na tabela e nos gráficos abaixo. Mas claramente percebemos que há uma melhora significativa de desempenho no caso de realizarmos os cálculos antes e armazenarmos em um array.
Execução |
Parametro | Tempo ms |
testePrimoCalcularUmPorUm | 100 | 19 |
testePrimoCalcularArray | 100 | 2 |
testePrimoCalcularUmPorUm | 1000 | 97 |
testePrimoCalcularArray | 1000 | 16 |
testePrimoCalcularUmPorUm | 10000 | 51959 |
testePrimoCalcularArray | 10000 | 115 |
Diego, você poderia postar a definição da função ehPrimo() ! Por acaso você usou algum crivo? Queria poder fazer uma comparaçao!
ResponderExcluirNeste caso utilizei a definição mais simples possível para é primo:
ResponderExcluirPara X se X != de 1:
Para i = 2; i < X ; i++ {
if (i!=X && X%i==0) return false;
}
return true