Comment vérifier si un nombre est premier en Java

Introduction

Dans ce laboratoire (lab), vous apprendrez à vérifier si un nombre est premier en Java. Nous commencerons par implémenter une boucle de base pour déterminer la primalité.

Ensuite, nous allons optimiser le processus de vérification des nombres premiers en utilisant la racine carrée du nombre. Enfin, nous améliorerons le code pour gérer de manière élégante les entrées négatives et non entières.

Skills Graph

Implémenter une boucle de vérification de nombre premier de base

Dans cette étape, nous allons écrire un programme Java pour vérifier si un nombre donné est un nombre premier en utilisant une boucle de base. Un nombre premier est un nombre naturel supérieur à 1 qui n'a pas de diviseurs positifs autres que 1 et lui-même.

1. Ouvrez le fichier HelloJava.java dans l'éditeur WebIDE s'il n'est pas déjà ouvert.

2. Remplacez tout le contenu du fichier par le code suivant :

   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();
       }
   }

   Comprenons les nouvelles parties de ce code :

   • Nous utilisons toujours la classe Scanner pour obtenir des entrées de l'utilisateur.
   • int number = scanner.nextInt(); : Cette ligne lit une valeur entière saisie par l'utilisateur et la stocke dans la variable number.
   • if (number <= 1) : Nous vérifions si le nombre est inférieur ou égal à 1. Les nombres inférieurs ou égaux à 1 ne sont pas considérés comme premiers.
   • boolean isPrime = true; : Nous introduisons une variable boolean appelée isPrime et l'initialisons à true. Nous l'utiliserons pour suivre si le nombre est premier.
   • for (int i = 2; i < number; i++) : Il s'agit d'une boucle for. Elle commence avec i égal à 2 et continue tant que i est inférieur au number. À chaque itération, i augmente de 1. Nous commençons à vérifier les diviseurs à partir de 2 car 1 est toujours un diviseur et nous recherchons des diviseurs autres que 1 et le nombre lui-même.
   • if (number % i == 0) : À l'intérieur de la boucle, cette ligne vérifie si le number est parfaitement divisible par i (le reste de la division est 0). Si c'est le cas, cela signifie que nous avons trouvé un diviseur autre que 1 et le nombre lui-même.
   • isPrime = false; : Si un diviseur est trouvé, nous définissons isPrime sur false.
   • break; : Cette instruction quitte immédiatement la boucle for. Une fois que nous avons trouvé un diviseur, nous savons que le nombre n'est pas premier, il n'y a donc pas besoin de vérifier plus loin.
   • Enfin, nous vérifions la valeur de isPrime pour afficher si le nombre est premier ou non.

3. Enregistrez le fichier (Ctrl+S ou Cmd+S).

4. Compilez le programme modifié dans le terminal :

   javac HelloJava.java

   S'il n'y a pas d'erreurs de compilation, un fichier HelloJava.class sera créé.

5. Exécutez le programme compilé :

   java HelloJava

6. Le programme vous demandera d'entrer un entier positif. Entrez un nombre (par exemple, 7) et appuyez sur Entrée. Le programme vous indiquera si le nombre est premier ou non. Essayez d'entrer différents nombres comme 4, 11, 1 ou 0 pour voir la sortie.

   Enter a positive integer: 7
   7 is a prime number.

   Enter a positive integer: 4
   4 is not a prime number.

Vous avez réussi à implémenter un vérificateur de nombres premiers de base en utilisant une boucle en Java !

Optimiser la vérification de nombres premiers avec la racine carrée

Dans l'étape précédente, notre boucle de vérification de nombres premiers itérait de 2 jusqu'au nombre lui-même. Bien que cela fonctionne, cela peut être inefficace pour des nombres très grands. Nous pouvons optimiser ce processus en vérifiant seulement les diviseurs jusqu'à la racine carrée du nombre.

Voici pourquoi cette optimisation fonctionne : Si un nombre n a un diviseur d supérieur à sa racine carrée (d > sqrt(n)), alors il doit y avoir un autre diviseur d' tel que d * d' = n. Cet autre diviseur d' doit être inférieur à la racine carrée (d' < sqrt(n)). Par conséquent, si un nombre a des diviseurs autres que 1 et lui-même, il doit avoir au moins un diviseur inférieur ou égal à sa racine carrée. Ainsi, nous n'avons besoin de vérifier les diviseurs que jusqu'à la racine carrée.

1. Ouvrez le fichier HelloJava.java dans l'éditeur WebIDE.

2. Modifiez la boucle for dans la méthode main pour qu'elle itère seulement jusqu'à la racine carrée du nombre. Remplacez le bloc de la boucle for existant par le code suivant :

   // ... (code précédent) ...
   
   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.");
       }
   }
   
   // ... (reste du code) ...

   Examinons les modifications :

   • int limit = (int) Math.sqrt(number); : Nous calculons la racine carrée du number en utilisant Math.sqrt(). Cette méthode retourne un double, donc nous le convertissons en int car notre compteur de boucle i est un entier. Nous stockons cette valeur dans une variable appelée limit.
   • for (int i = 2; i <= limit; i++) : La boucle itère maintenant de 2 jusqu'au limit calculé (la partie entière de la racine carrée) inclus.

3. Enregistrez le fichier (Ctrl+S ou Cmd+S).

4. Compilez le programme optimisé dans le terminal :

   javac HelloJava.java

   Encore une fois, s'il n'y a pas d'erreurs, un fichier HelloJava.class sera généré.

5. Exécutez le programme compilé :

   java HelloJava

6. Entrez différents nombres pour tester le vérificateur de nombres premiers optimisé. Vous devriez obtenir les mêmes résultats qu'avant, mais pour des nombres très grands, cette version sera plus rapide.

   Enter a positive integer: 29
   29 is a prime number.

   Enter a positive integer: 100
   100 is not a prime number.

Vous avez réussi à optimiser votre programme de vérification de nombres premiers en réduisant le nombre d'itérations de la boucle.

Gérer les entrées négatives et non entières

Dans les étapes précédentes, notre programme suppose que l'utilisateur entrera toujours un entier positif. Cependant, dans les applications réelles, les utilisateurs peuvent entrer des nombres négatifs, zéro ou même du texte non entier. Notre programme actuel ne gère pas ces cas de manière appropriée. Dans cette étape, nous ajouterons des vérifications pour gérer les entrées négatives et non entières.

1. Ouvrez le fichier HelloJava.java dans l'éditeur WebIDE.

2. Modifiez la méthode main pour inclure des vérifications pour les nombres négatifs et utilisez une boucle pour vous assurer que l'utilisateur entre un entier positif valide. Remplacez le code existant dans la méthode main par le suivant :

   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();
       }
   }

   Analysons les nouvelles ajouts :

   • import java.util.InputMismatchException; : Nous importons cette classe pour gérer les cas où l'utilisateur entre quelque chose qui n'est pas un entier.
   • int number = 0; boolean validInput = false; : Nous initialisons number et un indicateur boolean validInput.
   • while (!validInput) : Il s'agit d'une boucle while qui continuera à s'exécuter tant que validInput est false.
   • try { ... } catch (InputMismatchException e) { ... } : Il s'agit d'un bloc try-catch. Le code à l'intérieur du bloc try est exécuté. Si une InputMismatchException se produit (ce qui signifie que l'entrée n'était pas un entier), le code à l'intérieur du bloc catch est exécuté.
   • number = scanner.nextInt(); : Nous essayons de lire un entier.
   • if (number > 0) : À l'intérieur du bloc try, nous vérifions si le nombre entré est positif. Si c'est le cas, nous définissons validInput sur true pour sortir de la boucle.
   • System.out.println("Please enter a positive integer (greater than 0)."); : Si le nombre n'est pas positif, nous affichons un message d'erreur.
   • System.out.println("Invalid input. Please enter an integer."); : À l'intérieur du bloc catch, si une InputMismatchException se produit, nous affichons un message d'erreur.
   • scanner.next(); : Ceci est crucial à l'intérieur du bloc catch. Il consomme l'entrée invalide du scanner, empêchant une boucle infinie où le programme continue à essayer de lire la même entrée invalide.

3. Enregistrez le fichier (Ctrl+S ou Cmd+S).

4. Compilez le programme mis à jour :

   javac HelloJava.java

5. Exécutez le programme :

   java HelloJava

6. Maintenant, essayez d'entrer différents types d'entrées :

   • Entrez un entier positif (par exemple, 13).
   • Entrez un entier négatif (par exemple, -5).
   • Entrez zéro (0).
   • Entrez du texte (par exemple, "hello").

   Observez comment le programme gère ces différentes entrées, vous invitant à entrer un entier positif valide jusqu'à ce que vous le fassiez.

   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.

Vous avez réussi à rendre votre programme de vérification de nombres premiers plus robuste en gérant les nombres négatifs et les entrées non entières à l'aide d'une boucle et de la gestion des exceptions.

Résumé

Dans ce laboratoire (lab), nous avons appris à vérifier si un nombre est premier en Java. Nous avons commencé par implémenter une vérification de nombre premier de base en utilisant une boucle qui itère de 2 jusqu'au nombre moins un, en vérifiant la divisibilité. Cette approche initiale a fourni une compréhension fondamentale de la définition des nombres premiers et de son implémentation algorithmique.

Nous avons ensuite exploré des optimisations pour améliorer l'efficacité de la vérification de nombres premiers. Cela impliquait de comprendre que nous n'avons besoin de vérifier les diviseurs que jusqu'à la racine carrée du nombre, réduisant considérablement le nombre d'itérations nécessaires pour les entrées plus grandes. Enfin, nous avons traité les cas limites (edge cases) en gérant les nombres négatifs et les entrées non entières pour rendre notre fonction de vérification de nombres premiers plus robuste et complète.