Seu código original sem os comentários:[code]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);
}
}
}[/code]Vamos refatorar separando um método que determina se um número é primo ou não.[code]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;
}
}[/code]Bem, agora podemos nos concentrar na parte que importa. Determinar se um número é primo.
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).
Com isso, vamos otimizar mais: public static boolean isPrimo(int valor) {
for (int j = 2; j <= valor / j; j++) {
if (valor % j == 0) return false;
}
return true;
}
Ainda é possível fazer-se mais otimizações, explorando o fato de que o único primo par é o 2 (e dobrando o desempenho): 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;
}
Ainda é possível ir mais adiante, em otimizações. Mas este daí já deve dar uma melhora significativa no desempenho.
