pq esses dois códigos tem uma diferença de tempo tão grande na execução?
programa 1 (ESTE EXECUTA BEM MAIS RAPIDO)
public class PrimeNumbers {
public static boolean isPrime ( int num ) {
boolean prime = true;
int limit = (int) Math.sqrt ( num );
for ( int i = 2; i <= limit; i++ ) {
if ( num % i == 0 ) {
prime = false;
break;
}
}
return prime;
}
public static void main ( String[] args ) {
for ( int i = 100000 ; i <= 1000000; i++ ) {
if ( isPrime ( i ) && isPrime (i+2) )
System.out.println ( i + " and " + (i+2)+" ARE TWIN PRIMES!" );
}
}
}
programa 2 (ESTE EH MAIS DEVAGAR)
import java.util.ArrayList;
public class Primos2 {
public static void main(String args[]) {
ArrayList<Integer> segList = new ArrayList<Integer>();
int y=1, z=0, w=0, x=0;
int a;
for (x=100000; x<1000000; x++) {
a = (int) (x/2);
z=0;
for (y=2; y<a; y++) {
if (x%y == 0) {
z++;
break;
}
}
if (z == 0) {
segList.add(x);
if (w>0) {
if ( ((int)segList.get(w-1)) == ((int)segList.get(w)) - 2 ) {
System.out.println(((int)segList.get(w-1))+" and "+((int)segList.get(w))+" ARE TWIN PRIMES!");
}
}
w++;
}
}
}
}
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.
[quote=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.[/quote]
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
[quote=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[/quote]
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.
[quote=ViniGodoy][quote=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[/quote]
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.[/quote]
nossa, eh isso!
um eu botei pra testar soh ateh a raiz quadrada, o outro para testar até a metade do numero que esta sendo testado
nossa isso fez uma diferença imensa…
na verdade o correto eh testar soh ateh a raiz mesmo
que vacilo meu!
valeuzão
Um outro algoritmo interessante é esse aqui:
[code]public class PrimeNumbers {
private static Set primeList = new HashSet();
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!" );
}
}
} [/code]
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.
[quote=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.[/quote]
po velho brigadao!
vc se importa de fazer uns comentarios basicos nesse seu codigo soh pra me ajudar a entender melhor?
abraço!
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);
}
}