Você cometeu uns pequenos erros bobos.
O seu grande erro é que você não faz o counter
voltar para zero depois de iterar um número no i
. Por causa disso, após decidir que 1 não é primo, ele nunca mais será capaz de decidir que número nenhum é primo, uma vez que counter
nunca diminui.
Outro probleminha era a condição de parada do for
que estava 1 <= 100
ao invés de i <= 100
.
Por fim, você pode declarar as variáveis i
e k
dentro do próprio for
, não precisa declarar antes.
Faltou acrescentar um espaço antes do "is prime"
.
Assim, aqui está o seu código corrigido.
public class Main {
public static void main(String args[]) {
for (int i = 1; i <= 100; i++) {
int counter = 0;
for (int k = 1; k <= i; k++) {
if (i % k == 0) ++counter;
}
if (counter == 2) {
System.out.println("The number: " + i + " is prime");
}
}
}
}
Também é possível otimizar o seu código um pouco mais, pois você não precisa nunca testar se o número é divisível por 1 ou por ele mesmo, porque sempre será. Desta forma, você não precisará mais contar os divisores, pois assim que você acha um divisor já sabe que o número é composto e nem precisa perder tempo testando os demais números, podendo usar o continue
para seguir para a próxima iteração. Isso também elimina a necessidade de haver a variável counter
. Desta forma, o seu código fica assim:
public class Main {
public static void main(String args[]) {
out: for (int i = 1; i <= 100; i++) {
for (int k = 2; k < i; k++) {
if (i % k == 0) continue out;
}
System.out.println("The number: " + i + " is prime");
}
}
}
Dá para otimizar ainda mais se você verificar que se o número é composto, então pelo menos um dos divisores é menor ou igual a raiz quadrada do número. Assim, se até chegar na raiz quadrada, você não encontrar nenhum divisor, é porque o número é primo. Logo:
public class Main {
public static void main(String args[]) {
out: for (int i = 1; i <= 100; i++) {
for (int k = 2; k <= Math.sqrt(i); k++) {
if (i % k == 0) continue out;
}
System.out.println("The number: " + i + " is prime");
}
}
}
Há outros truques matemáticos possíveis, em especial para evitar testar valores de k
que são compostos e também para computar a raiz quadrada inteira que é mais rápido que a raiz quadrada de ponto flutuante. Outras propriedades de números primos e compostos podem ser utilizadas para reduzir-se o esforço computacional. Entretanto, estas otimizações mais agressivas já não seriam simples, e você provavelmente quer um algoritmo que seja bem simples, ainda mais que você só está testando os primos até o número 100.