Java e otimização

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

Tem esta forma aqui:

https://www.staroski.com.br/posts/4

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.

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?

Vou dar uma olhada mano, obrigado

Respondendo sua pergunta com uma pergunta e passando na frente do @staroski :wink:

Qual o único número primo que é par?

É um bom exemplo de aplicação de programação dinâmica também se precisar ficar fazendo a pergunta em um intervalo específico :wink:

apenas o 2

Se só o 2 é primo e par, pra que verificar os outros números pares? Isso responde sua pergunta inicial.

Entendo, isso reduziria muito msm, acho que eu tava muito cansado para pensar
Valeu mano

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

1 curtida

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:

1 curtida

Sim! Tem a questão da raiz tbm!

1 curtida

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

Meu professor da faculdade não permitiu usar coisas que ele ainda não ensinou no programa (como booleanos)
Então adaptei para isso


Ele ficou um pouco mais devagar, mas muito mais rápido comparado a primeira versão
Valeu mesmo
Ajudou demais

Muito legal mano
Eu salvei para estudar um pouco, porque no momento não entendi muito algumas partes