Boa noite galera
Teria como eu otimizar esse código
Ele calcula os 10 mil primeiros números primos
No momento ele esta rodando em 18 segundos
Queria deixar ele mais rápido
Java e otimização
T
15 Respostas
S
A
O código do @staroski já dá uma boa melhorada no que você fez. Para testes genéricos do tipo “O número X é primo?” deve ser bom o suficiente.
No seu caso, você quer saber o 10000 “ésimo” número primo (eu não lembro mais ordinais pra milhares).
Numa situação dessa, saber os números primos anteriores pode otimizar muito todo o processo.
Dá uma procurada no Crivo de Eratóstenes. Vai retornar resultados MUITO mais rápido.
T
Cara ficou muito mais rapido, valeu mesmo
Mas por quê?
Tipo ele n executa um por vez da msm forma?
Ou ele separa quando é par e impar?
T
Vou dar uma olhada mano, obrigado
D
Respondendo sua pergunta com uma pergunta e passando na frente do @staroski 
Qual o único número primo que é par?
D
É um bom exemplo de aplicação de programação dinâmica também se precisar ficar fazendo a pergunta em um intervalo específico
T
apenas o 2
D
Se só o 2 é primo e par, pra que verificar os outros números pares? Isso responde sua pergunta inicial.
T
Entendo, isso reduziria muito msm, acho que eu tava muito cansado para pensar
Valeu mano
D
1 like
Reduz à metade. Parece ser absurdamente melhor, mas para conjuntos de números arbitrariamente grandes, por incrível que pareça, não faz muita diferença. Aí que entram métodos mais específicos como o Crivo de Eratóstenes mencionado pelo @AbelBueno
S
1 like
Primeiro porque ele só vai iterando os números ímpares.
Segundo porque não é necessário avaliar todos os divisores até chegar ao número alvo.
Qualquer divisor do número maior que a sua raiz quadrada é múltiplo de um divisor menor já testado.
Desta forma, o código pode ser corrigido, de maneira a que o ciclo de repetição pare assim que alcance a raiz quadrada do número que pretendemos testar, por isso que o for compara se o quadrado do número atual é menor que o número alvo, o link a seguir explica isso:
D
1 like
Sim! Tem a questão da raiz tbm!
D
Só de “brincadeira”:
import java.util.Set;
import java.util.TreeSet;
/**
*
* @author David
*/
public class CrivoEratostenes {
public static Set<Integer> primos( int max ) {
Set<Integer> primos = new TreeSet<>();
boolean[] crivo = new boolean[max + 3]; // 0, 1 e max
int limite = (int) Math.sqrt( max );
for ( int i = 2; i <= limite; i++ ) {
if ( !crivo[i] ) {
int c = 2;
while ( i * c <= max ) {
crivo[i*c++] = true;
}
}
}
for ( int i = 2; i <= max; i++ ) {
if ( !crivo[i] ) {
primos.add( i );
}
}
return primos;
}
public static void main( String[] args ) {
long inicio;
long fim;
// escala logarítmica
for ( int i = 10; i <= 100000000; i *= 10 ) {
inicio = System.currentTimeMillis();
primos( i );
fim = System.currentTimeMillis();
System.out.println( "Números primos de 0 a " + i );
System.out.println( " " + ( fim - inicio ) + " milisegundos" );
}
}
}
Na minha máquina:
Números primos de 0 a 10
0 milisegundos
Números primos de 0 a 100
0 milisegundos
Números primos de 0 a 1000
1 milisegundos
Números primos de 0 a 10000
3 milisegundos
Números primos de 0 a 100000
5 milisegundos
Números primos de 0 a 1000000
20 milisegundos
Números primos de 0 a 10000000
139 milisegundos
Números primos de 0 a 100000000
1946 milisegundos
Claro, tem a sobrecarga da inserção dos dados no TreeSet para permitir consultas rápidas na ordem de O(lg n), mas como as inserções tbm são O(lg n) isso não é problema. O que “pega” é percorrer o crivo para verificar os primos e inserir no conjunto. Se formos considerar só a criação do crivo, o que bastaria para executar as consultas, considerando que um valor falso no array indica que o número é primo, fica ainda mais rápido.
Algo como:
public class CrivoEratostenes {
public static void primos( int max ) {
boolean[] crivo = new boolean[max + 3];
int limite = (int) Math.sqrt( max );
for ( int i = 2; i <= limite; i++ ) {
if ( !crivo[i] ) {
int c = 2;
while ( i * c <= max ) {
crivo[i*c++] = true;
}
}
}
}
public static void main( String[] args ) {
long inicio;
long fim;
// escala logarítmica
for ( int i = 10; i <= 100000000; i *= 10 ) {
inicio = System.currentTimeMillis();
primos( i );
fim = System.currentTimeMillis();
System.out.println( "Números primos de 0 a " + i );
System.out.println( " " + ( fim - inicio ) + " milisegundos" );
}
}
}
Na minha máquina:
Números primos de 0 a 10
0 milisegundos
Números primos de 0 a 100
0 milisegundos
Números primos de 0 a 1000
0 milisegundos
Números primos de 0 a 10000
0 milisegundos
Números primos de 0 a 100000
1 milisegundos
Números primos de 0 a 1000000
5 milisegundos
Números primos de 0 a 10000000
36 milisegundos
Números primos de 0 a 100000000
806 milisegundos
T
T
Muito legal mano
Eu salvei para estudar um pouco, porque no momento não entendi muito algumas partes
Criado 9 de abril de 2022
Ultima resposta 10 de abr. de 2022
Respostas 15
Participantes 4
Alura Git Flow: entenda o que é, como e quando utilizar Entenda o que é Git Flow, como funciona seu fluxo com branches como Master, Develop, Feature, Release e Hotfix, além de vantagens e desvantagens.
Casa do Codigo Apache Kafka e Spring Boot: Comunicacao assincrona entre... Por Eduardo Felipe Zambom Santana — Casa do Codigo