Lógica número primo

O meio mais fácil de você entender é pegar um debugger (uma IDE qualquer, como o Eclipse ou o Netbeans) e ir executando esse programa passo-a-passo e olhar os valores das variáveis. Você consegue fazer isso?

kra… esse codigo faz o seguinte…

o primeiro for vai escolhe de 2 até nvalor o numero que será testado.

o segundo testa se o mesmo é divisivel por 2,3,4,5,6… até (nvalor -1). Se for divisivel por qulquer um desses ele não será primo.
Sugiro que otimize o algoritmo trocando o segundo for para:

for(int j = 2; j < (i/2); j++) {

…

}

pois faz a metade das comparações e nenhum numero é divisivel por outro maior que a metade dele.

abraço

Rodrigo

Obrigado aos colegas thingol e Rasalves acima pela ajuda.
Quanto a usar o depurador vi no guru(Google) e achei esse link:

Vou criar um mini-tuto no youtube para explicar aos iniciantes como eu como usar o depurador.

Cara, o depurador é uma boa idéia sim.
Mas uma coisa: tá caro pra danar esse seu código.

Só um detalhe: O número 2 é o único primo par. Do mesmo modo, não há primos terminados em 0 e 5 (com exceção do último caso, do próprio 5).

Com os dois for, o programa testa todas as combinações possíveis para verificar se o número é primo. A parte do if vê se j é mútiplo de i.

Na execução dos primeiros valores, ficaria do seguinte modo (supondo nValor = 3):
i = 2 até 3, e
j = 2; j < i

i = 2
j = 2 (até 2 < 2 ) - FALSO
<a parte do if é pulada>
Portanto, imprime primo

i = 3

j = 2 (até 2 < 3)

2 é mútiplo de 3? FALSO

j = 3 (até 3 < 3) - FALSO

<a parte do if é pulada>

Portanto, imprime primo

i = 4
j = 2 (até 2 < 4)
2 é mútiplo de 4? VERDADEIRO
O programa sai do laço pelo break e não imprime.

Com isso, acaba-se a execução.

Mas, como já disseram, dá pra otimizar o código, fazendo com que ele procure por menos números. O mínimo que se pode procurar é a parte inteira da raiz quadrada. Por exemplo, para verificar se o número 100 é primo, basta procurar entre 2 e 10.

E é claro que se pode usar o tal do “Crivo de Eratóstenes”.

Achei este código muito complicado.
Tempos atrás fiz uma classe que testa se o número é primo. Se alguém quiser posso disponibilizar a classe.

O Avencurt, oloca sim a classe.

Eu tenho o mesmo codigo que foi citado acima, mas gostaria de ver esse outro para poder comparar e ate mesmo se conseguir melhora-lo

Crivo de Eratóstenes

public class Primos {

    public static void main(String[] args) {
        int nValor = 8;
        boolean primo = true;

        for (int i = 2; i <= nValor; i++) {
            primo = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    primo = false;
                    break;
                }
            }

            if (primo) System.out.println(i);
        }
    }
}

public class Primos {

    public static void main(String[] args) {
        int nValor = 8;

        for (int i = 2; i <= nValor; i++) {
            if (isPrimo(i)) System.out.println(i);
        }
    }

    public static boolean isPrimo(int valor) {
        for (int j = 2; j < valor; j++) {
            if (valor % j == 0) return false;
        }
        return true;
    }
}

Primeiramente, todo número composto (ou seja, não-primo) é o produto de pelo menos dois outros números inteiros. Por exemplo, 58=2x29. Um número grande nunca será divisível por algo maior que a sua metade. Por isso, ao tentar dividir um número como 101 por exemplo por 50, já podemos desistir de qualquer número entre 51 e 100, pois o quociente será menor que dois, e portanto não será inteiro.

Por outro lado, se o número não é divisível por 2, então não apenas qualquer coisa além da sua metade vai falhar, como qualquer coisa além de sua terça parte vai falhar. Se ele não for divisível por 5, qualquer coisa além de sua quinta parte vai falhar.

Assim, Se sabemos que o N não é divisível por dois, ele também não é divisível por N/2. Se não é divisível por 3, também não é por N/3. Se não é divisível por 4 também não é por N/4. Se não é por 5, também não é por N/5. Se não é divisível por J, não será para N/J. Logo, quando J for maior que N/J saberemos que o número é primo. Esse ponto onde J = N/J é a raiz quadrada de N. Mas ao invés de determinar a raiz quadrada de N (algo que é computacionalmente caro), podemos nos ater a definição de que se J = N/J então J=sqrt(N).

public static boolean isPrimo(int valor) {
        for (int j = 2; j <= valor / j; j++) {
            if (valor % j == 0) return false;
        }
        return true;
    }

public static boolean isPrimo(int valor) {
        if (valor == 2) return true;
        for (int j = 3; j <= valor / j; j += 2) {
            if (valor % j == 0) return false;
        }
        return true;
    }

Segue a classe e um prog para testar se um número é primo até o limite de Long. E para testar um número específico basta remover o for e informar direto o número.

As críticas serão bem-vindas.

Valeu a todos, guj é o maior e melhor fórum de Java.