Como Verificar se um Número é Primo em Java - Guia Completo

Introdução

Neste laboratório, você aprenderá como verificar se um número é primo em Java. Começaremos implementando um loop básico para determinar a primalidade.

Em seguida, otimizaremos o processo de verificação de números primos utilizando a raiz quadrada do número. Por fim, aprimoraremos o código para lidar com entradas negativas e não inteiras de forma adequada.

Implementar Loop Básico de Verificação de Primos

Nesta etapa, escreveremos um programa Java para verificar se um determinado número é um número primo usando um loop básico. Um número primo é um número natural maior que 1 que não possui divisores positivos além de 1 e ele mesmo.

Abra o arquivo HelloJava.java no editor WebIDE, caso ainda não esteja aberto.
Substitua todo o conteúdo do arquivo pelo seguinte código:
```
import java.util.Scanner;

public class HelloJava {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter a positive integer: ");
        int number = scanner.nextInt();

        if (number <= 1) {
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            for (int i = 2; i < number; i++) {
                if (number % i == 0) {
                    isPrime = false;
                    break; // Exit the loop early if a divisor is found
                }
            }

            if (isPrime) {
                System.out.println(number + " is a prime number.");
            } else {
                System.out.println(number + " is not a prime number.");
            }
        }

        scanner.close();
    }
}
```
Vamos entender as novas partes deste código:
- Ainda usamos o Scanner para obter a entrada do usuário.
- int number = scanner.nextInt();: Esta linha lê um valor inteiro inserido pelo usuário e o armazena na variável number.
- if (number <= 1): Verificamos se o número é menor ou igual a 1. Números menores ou iguais a 1 não são considerados primos.
- boolean isPrime = true;: Introduzimos uma variável boolean chamada isPrime e a inicializamos como true. Usaremos isso para acompanhar se o número é primo.
- for (int i = 2; i < number; i++): Este é um loop for. Ele começa com i em 2 e continua enquanto i for menor que o number. Em cada iteração, i aumenta em 1. Começamos a verificar os divisores a partir de 2 porque 1 é sempre um divisor e estamos procurando divisores diferentes de 1 e do próprio número.
- if (number % i == 0): Dentro do loop, esta linha verifica se o number é perfeitamente divisível por i (o resto da divisão é 0). Se for, significa que encontramos um divisor diferente de 1 e do próprio número.
- isPrime = false;: Se um divisor for encontrado, definimos isPrime como false.
- break;: Esta instrução sai imediatamente do loop for. Uma vez que encontramos um divisor, sabemos que o número não é primo, então não há necessidade de verificar mais.
- Finalmente, verificamos o valor de isPrime para imprimir se o número é primo ou não.
Salve o arquivo (Ctrl+S ou Cmd+S).
Compile o programa modificado no Terminal:
```
javac HelloJava.java
```
Se não houver erros de compilação, um arquivo HelloJava.class será criado.
Execute o programa compilado:
```
java HelloJava
```
O programa solicitará que você insira um inteiro positivo. Insira um número (por exemplo, 7) e pressione Enter. O programa informará se o número é primo ou não. Tente inserir números diferentes como 4, 11, 1 ou 0 para ver a saída.
```
Enter a positive integer: 7
7 is a prime number.
```
```
Enter a positive integer: 4
4 is not a prime number.
```

Você implementou com sucesso um verificador de números primos básico usando um loop em Java!

Otimizar Verificação de Primos com Raiz Quadrada

Na etapa anterior, nosso loop de verificação de primos iterava de 2 até o próprio número. Embora isso funcione, pode ser ineficiente para números muito grandes. Podemos otimizar isso verificando apenas os divisores até a raiz quadrada do número.

Aqui está o porquê dessa otimização funcionar: Se um número n tem um divisor d maior que sua raiz quadrada (d > sqrt(n)), então deve haver outro divisor d' tal que d * d' = n. Este outro divisor d' deve ser menor que a raiz quadrada (d' < sqrt(n)). Portanto, se um número tiver algum divisor diferente de 1 e ele mesmo, ele deve ter pelo menos um divisor menor ou igual à sua raiz quadrada. Então, só precisamos verificar os divisores até a raiz quadrada.

Abra o arquivo HelloJava.java no editor WebIDE.

Modifique o loop for no método main para iterar apenas até a raiz quadrada do número. Substitua o bloco de loop for existente pelo seguinte código:

// ... (previous code) ...

if (number <= 1) {
    System.out.println(number + " is not a prime number.");
} else {
    boolean isPrime = true;
    // Optimize the loop to check up to the square root
    int limit = (int) Math.sqrt(number);
    for (int i = 2; i <= limit; i++) {
        if (number % i == 0) {
            isPrime = false;
            break; // Exit the loop early if a divisor is found
        }
    }

    if (isPrime) {
        System.out.println(number + " is a prime number.");
    } else {
        System.out.println(number + " is not a prime number.");
    }
}

// ... (rest of the code) ...

Vamos analisar as mudanças:

int limit = (int) Math.sqrt(number);: Calculamos a raiz quadrada do number usando Math.sqrt(). Este método retorna um double, então o convertemos para um int porque nosso contador de loop i é um inteiro. Armazenamos este valor em uma variável chamada limit.
for (int i = 2; i <= limit; i++): O loop agora itera de 2 até e incluindo o limit calculado (a parte inteira da raiz quadrada).

Salve o arquivo (Ctrl+S ou Cmd+S).
Compile o programa otimizado no Terminal:
```
javac HelloJava.java
```
Novamente, se não houver erros, um arquivo HelloJava.class será gerado.
Execute o programa compilado:
```
java HelloJava
```
Insira números diferentes para testar o verificador de primos otimizado. Você deve obter os mesmos resultados de antes, mas para números muito grandes, esta versão será mais rápida.
```
Enter a positive integer: 29
29 is a prime number.
```
```
Enter a positive integer: 100
100 is not a prime number.
```

Você otimizou com sucesso seu programa de verificação de números primos, reduzindo o número de iterações no loop.

Lidar com Entradas Negativas e Não Inteiras

Nas etapas anteriores, nosso programa assume que o usuário sempre inserirá um inteiro positivo. No entanto, em aplicações do mundo real, os usuários podem inserir números negativos, zero ou até mesmo texto não inteiro. Nosso programa atual não lida com esses casos de forma adequada. Nesta etapa, adicionaremos verificações para lidar com entradas negativas e não inteiras.

Abra o arquivo HelloJava.java no editor WebIDE.

Modifique o método main para incluir verificações de números negativos e use um loop para garantir que o usuário insira um inteiro positivo válido. Substitua o código existente dentro do método main pelo seguinte:

import java.util.Scanner;
import java.util.InputMismatchException; // Import this class

public class HelloJava {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number = 0;
        boolean validInput = false;

        // Loop until valid positive integer input is received
        while (!validInput) {
            System.out.print("Enter a positive integer: ");
            try {
                number = scanner.nextInt();
                if (number > 0) {
                    validInput = true; // Input is valid, exit loop
                } else {
                    System.out.println("Please enter a positive integer (greater than 0).");
                }
            } catch (InputMismatchException e) {
                System.out.println("Invalid input. Please enter an integer.");
                scanner.next(); // Consume the invalid input to prevent infinite loop
            }
        }

        // Now, perform the prime check on the valid positive number
        if (number <= 1) { // This check is technically redundant now due to the input loop, but good for clarity
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            int limit = (int) Math.sqrt(number);
            for (int i = 2; i <= limit; i++) {
                if (number % i == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                System.out.println(number + " is a prime number.");
            } else {
                System.out.println(number + " is not a prime number.");
            }
        }

        scanner.close();
    }
}

Vamos detalhar as novas adições:

import java.util.InputMismatchException;: Importamos esta classe para lidar com casos em que o usuário insere algo que não é um inteiro.
int number = 0; boolean validInput = false;: Inicializamos number e uma flag boolean validInput.
while (!validInput): Este é um loop while que continuará a ser executado enquanto validInput for false.
try { ... } catch (InputMismatchException e) { ... }: Este é um bloco try-catch. O código dentro do bloco try é executado. Se ocorrer uma InputMismatchException (significando que a entrada não era um inteiro), o código dentro do bloco catch é executado.
number = scanner.nextInt();: Tentamos ler um inteiro.
if (number > 0): Dentro do bloco try, verificamos se o número inserido é positivo. Se for, definimos validInput como true para sair do loop.
System.out.println("Please enter a positive integer (greater than 0).");: Se o número não for positivo, imprimimos uma mensagem de erro.
System.out.println("Invalid input. Please enter an integer.");: Dentro do bloco catch, se ocorrer uma InputMismatchException, imprimimos uma mensagem de erro.
scanner.next();: Isso é crucial dentro do bloco catch. Ele consome a entrada inválida do scanner, impedindo um loop infinito onde o programa continua tentando ler a mesma entrada inválida.

Salve o arquivo (Ctrl+S ou Cmd+S).
Compile o programa atualizado:
```
javac HelloJava.java
```
Execute o programa:
```
java HelloJava
```
Agora, tente inserir diferentes tipos de entrada:
- Insira um inteiro positivo (por exemplo, 13).
- Insira um inteiro negativo (por exemplo, -5).
- Insira zero (0).
- Insira texto (por exemplo, "hello").
Observe como o programa lida com essas diferentes entradas, solicitando que você insira um inteiro positivo válido até que o faça.
```
Enter a positive integer: -5
Please enter a positive integer (greater than 0).
Enter a positive integer: 0
Please enter a positive integer (greater than 0).
Enter a positive integer: hello
Invalid input. Please enter an integer.
Enter a positive integer: 17
17 is a prime number.
```

Você tornou seu programa de verificação de primos mais robusto, lidando com números negativos e entradas não inteiras usando um loop e tratamento de exceções.

Resumo

Neste laboratório, aprendemos como verificar se um número é primo em Java. Começamos implementando uma verificação de primo básica usando um loop que itera de 2 até o número menos um, verificando a divisibilidade. Essa abordagem inicial forneceu uma compreensão fundamental da definição de número primo e sua implementação algorítmica.

Em seguida, exploramos otimizações para melhorar a eficiência da verificação de primos. Isso envolveu a compreensão de que só precisamos verificar os divisores até a raiz quadrada do número, reduzindo significativamente o número de iterações necessárias para entradas maiores. Finalmente, abordamos casos extremos, lidando com números negativos e entradas não inteiras para tornar nossa função de verificação de primos mais robusta e completa.