Off-topic

Programação Java
#1

off-topic

#2

Vou te passar mais ou menos o esquema, mas implementar é contigo…

  1. Um numero primo é divisível apenas por 1 e por ele mesmo. Logo, vc tem que checar se, entre todas os restos da divisão entre o número que vc quer verificar se é primo e os números menores que este, é zero. Se pelo menos um destes restos for zero, o número não é primo.

  2. Algumas coisas podem ser otimizadas nesta idéia: Você não precisa verificar a divisão por todos os números, mas sim apenas pelos primos já encontrados. Primos são sempre impares, então vc não precisa verificar números pares. Você precisa verificar a divisão apenas para números menores ou iguais a raiz quadrada de quem vc quer verificar se é primo.

exemplo: numeros primos menores que 100

==>inclua 2 na lista dos primos (o único primo que é par)
==> inclua tbm o 3, 5 e o 7 na lista dos primos.
==> de i = 2 até raizquadrada(proximo numero a verificar, começa com 9 e vai embora…), com incremento de dois em dois (para pegar somente os impares), faça {

se o resto da divisão entre o numero sendo verificado e o numero em primos[i] for zero, retorne primo = verdadeiro (e adicione este numero na lista dos primos), senão continue.

}

==> se este laço terminar para todos os valores até raizquadrada do numero atual, o numero atual não é primo.

Abraço!

#3

off-topic

#4

a) Procure por “Crivo de Erastótenes” ou “Erasthotenes Sieve”.
b) O crivo acima usa um vetor. Depois de calcular todos os primos, percorra o vetor, verificando quais dos números são primos, e adicione a um ArrayList.

#5

off-topic

#6 
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 &lt= sqrtN) {
            for (int i = j + j; i &lt n; i += j) {
                bs.clear (i);
            }
            j = bs.nextSetBit (j+1);
        }
        return bs;
    }

    
    public static void main(String[] args) {
        Sieve s = new Sieve(Integer.parseInt (args[0]));
        long t = System.currentTimeMillis();
        BitSet bs = s.sieve();
        System.out.println (System.currentTimeMillis() - t);
        System.out.println (bs.cardinality()); // números de primos entre 1 e n - 1
    }
}
#7

[quote=cassio]Vou te passar mais ou menos o esquema, mas implementar é contigo…

  1. Um numero primo é divisível apenas por 1 e por ele mesmo. Logo, vc tem que checar se, entre todas os restos da divisão entre o número que vc quer verificar se é primo e os números menores que este, é zero. Se pelo menos um destes restos for zero, o número não é primo.

  2. Algumas coisas podem ser otimizadas nesta idéia: Você não precisa verificar a divisão por todos os números, mas sim apenas pelos primos já encontrados. Primos são sempre impares, então vc não precisa verificar números pares. Você precisa verificar a divisão apenas para números menores ou iguais a raiz quadrada de quem vc quer verificar se é primo.

exemplo: numeros primos menores que 100

==>inclua 2 na lista dos primos (o único primo que é par)
==> inclua tbm o 3, 5 e o 7 na lista dos primos.
==> de i = 2 até raizquadrada(proximo numero a verificar, começa com 9 e vai embora…), com incremento de dois em dois (para pegar somente os impares), faça {

se o resto da divisão entre o numero sendo verificado e o numero em primos[i] for zero, retorne primo = verdadeiro (e adicione este numero na lista dos primos), senão continue.

}

==> se este laço terminar para todos os valores até raizquadrada do numero atual, o numero atual não é primo.

Abraço!

[/quote]

Opa, dei mancada ali! ahuahuaua Troquei as bolas quando fui explicar o algorítmo! A idéia é inversa, se o resto for zero para alguma divisão, então não é primi e vc pode pular fora do laço. Se chegar ao fim do laço sem encontrar nenhum resto = 0, então é primo, adicione este número na lista!

==> INICIO
==>inclua 2 na lista dos primos (o único primo que é par)
==> inclua tbm o 3, 5 e o 7 na lista dos primos.
==> de i = 2 até raizquadrada(proximo numero a verificar, começa com 9 e vai embora…), com incremento de dois em dois (para pegar somente os impares), faça {

se o resto da divisão entre o numero sendo verificado e o numero em primos[i] for zero, retorne primo = FALSO e caia fora do laço com um break.

}

==> se este laço terminar para todos os valores até raizquadrada do numero atual, o numero atual é primo. Adicione-o na lista!

Abraço!

#8