diferença no tempo de execução

Já tentou usar os dois programas na VisualVM e ver onde está pegando?

Uma coisa… para que vc fica testando se pares não são primos? Fora o 2, nenhum par é primo (pois todos são divisíveis por 2).
Faça seu for pular de 2 em 2 e dobre a velocidade de execução dos dois algoritmos.

ViniGodoy:

Já tentou usar os dois programas na VisualVM e ver onde está pegando?

Uma coisa… para que vc fica testando se pares não são primos? Fora o 2, nenhum par é primo (pois todos são divisíveis por 2).
Faça seu for pular de 2 em 2 e dobre a velocidade de execução dos dois algoritmos.

boa ideia, vou tentar
isso ae de pular os numeros pares n vai adiantar mto pq nos dois programas a primeira coisa q eles fazem eh dividir o numero em teste por dois, se nao tiver resto ele ja da o break e parte pro proximo

arthuraml:

boa ideia, vou tentar
isso ae de pular os numeros pares n vai adiantar mto pq nos dois programas a primeira coisa q eles fazem eh dividir o numero em teste por dois, se nao tiver resto ele ja da o break e parte pro proximo

Sim, mas é uma otimização muito fácil de fazer. Basta trocar o i++ do for por i += 2.
E, no seu caso, evita o teste de 450.000 números (e o consequente cálculo da raiz quadrada para eles, que é uma operação relativamente cara).

Agora, uma coisa que sugere que o primeiro seja mais rápido é que vc testa apenas até a raiz quadrada do número. E isso inclui poucos números.

ViniGodoy:

arthuraml:

boa ideia, vou tentar
isso ae de pular os numeros pares n vai adiantar mto pq nos dois programas a primeira coisa q eles fazem eh dividir o numero em teste por dois, se nao tiver resto ele ja da o break e parte pro proximo

Sim, mas é uma otimização muito fácil de fazer. Basta trocar o i++ do for por i += 2.
E, no seu caso, evita o teste de 450.000 números (e o consequente cálculo da raiz quadrada para eles, que é uma operação relativamente cara).

Agora, uma coisa que sugere que o primeiro seja mais rápido é que vc testa apenas até a raiz quadrada do número. E isso inclui poucos números.

valeuzão

Um outro algoritmo interessante é esse aqui:

public class PrimeNumbers {  

   private static Set<Integer> primeList = new HashSet<Integer>();

   static {
      primeList.add(2);
      for (int i = 3; i < 318; i+=2) {
            isPrime(i);
      }
   }

   public static boolean isPrime ( int num ) {  
      if (primeList.contains(num)) {
          return true;
      }

      int numSqr = Math.sqrt(num);
      for (Integer prime : primeList) {
         if (prime > numSqr)
             break;

         if (num % prime.intValue() == 0)
            return false;
      }

      prime.add(num);
      return true;
   }

   public static void main ( String[] args ) {  
      for ( int i = 100001 ; i <= 1000000; i+=2 ) {  
         if ( isPrime ( i ) && isPrime (i+2) )  
            System.out.println ( i + " and " + (i+2)+" ARE TWIN PRIMES!" );  
         }  
   }  
}

Infelizmente ele precisa da lista completa de todos os primos menores que a raiz quadrada do primeiro número a ser testado.
Mas ele é muito rápido, pois só irá fazer a divisão pelos primos menores que esse valor. Não por todos os divisores que já tem multiplos primos.

Fiz uma pequena correção ali. Antes de começar o for, é bom testar se o número já está na lista de primos e, portanto é primo.

Note que isso evitará calculos repetidos. Por exemplo, quando vc obter um i+2 que é primo, não precisará descobrir novamente se ele é primo ou não quando for testa-lo contra i+4, duas etapas do for na frente.

ViniGodoy:

Fiz uma pequena correção ali. Antes de começar o for, é bom testar se o número já está na lista de primos e, portanto é primo.

Note que isso evitará calculos repetidos. Por exemplo, quando vc obter um i+2 que é primo, não precisará descobrir novamente se ele é primo ou não quando for testa-lo contra i+4, duas etapas do for na frente.

po velho brigadao!
vc se importa de fazer uns comentarios basicos nesse seu codigo soh pra me ajudar a entender melhor?
abraço!

http://www.guj.com.br/posts/list/43972.java#233496

Chegou a testar a velocidade de execução dele? Estou sem java aqui e não fiz os testes.

A idéia central dele é simples. Um cache de números primos.

Veja o lado matemático da coisa.

Se um número não for divisível por 2 e nem por 3, ele obviamente não será divisível por 6.
Afinal, 2 e 3 são os multiplos inferiores de 6 (2x3=6). Um número divisível por 6 é, então, obrigatoriamente, divisível por 2 e 3 ao mesmo tempo.

A mesma lógica vale para o 4. Se o número não é divisível por 2, não será também por 4. Afinal, a tabuada do 4 nada mais é do que a do 2, multiplicada por 2.

Com isso, vc conclui o seguinte: Não é necessário dividir o número por todos os inferiores raiz quadrada dele para testar se é o não primo.
Mas sim, testar por todos os primos inferiores a raiz quadrada dele. Os demais números, seriam produtos de dois primos.

Agora, para que vc só teste por primos, é necessário conhecer os primos. É isso que aquele set faz.
Esse é um exemplo de otimização que gasta memória para ganhar tempo de execução.

Outra vantagem do set é que ele é capaz de eliminar imediatamente um primo já conhecido.
Por isso, em testes de pares como
5 e 7
7 e 9

o 7 não será testado duas vezes. Na primeira iteração ele já será incluído no set de primos. Na segunda, como ele estará dentro do set, não é feito calculo nenhum, e o algoritmo diz instantaneamente que 7 não é primo.

Essa seria uma otimização sugerida. Usar o crivo para criar o set de primos.

Eu procurei evita-la pois o crivo não é tão intuitivo quanto cálculos já conhecidos da matemática do segundo grau.

Aproveitando o código do Thingol, vi que leva 74 ms (no meu notebook, Core2Duo 2.1 Ghz) para achar os primos gêmeos entre 2 e 1000000. (É claro que se quiser achar os entre 100000 e 1000000 basta mudar um pouco o programa abaixo.

import java.util.*;  
   
 class Sieve {  
   
     private BitSet bs;  
     private int n;  
     public Sieve (int n) {  
         this.n = n;  
         bs = new BitSet (n);  
         bs.flip (2, n - 1); // 1 é primo?  
     }  
     public BitSet sieve() {  
         int sqrtN = (int) Math.sqrt (n);  
         int j = 2;  
         while (j <= sqrtN) {  
             for (int i = j + j; i < n; i += j) {  
                 bs.clear (i);  
             }  
             j = bs.nextSetBit (j+1);  
         }  
         return bs;  
     }  
   }
 class TwinPrimes {

	
     public static void main(String[] args) {  
	     
         Sieve s = new Sieve(1000000 + 1);  
         long t = System.currentTimeMillis();  
         BitSet bs = s.sieve();
         // Agora achando os primos gêmeos
         BitSet twinPrimes = new BitSet (1000000 + 1);
         for (int i = 3; i < 1000000 - 2; i += 2) {
		     if (bs.get(i) && bs.get (i+2)) {
			     twinPrimes.set(i); twinPrimes.set(i+2);
			 }
         }		 
         System.out.println ("Levou " + (System.currentTimeMillis() - t) + "ms para achar " + twinPrimes.cardinality() + " primos gêmeos");  
         System.out.println (twinPrimes);
     }  
 }