Java Programme pour vérifier les nombres premiers avec exemple

Qu'est-ce qu'un nombre premier?

Un nombre premier est un nombre naturel supérieur à 1 qui n'est divisible que par 1 ou par lui-même. Par exemple, 11 n'est divisible que par 1 ou par lui-même. Les autres nombres premiers sont 2, 3, 5, 7, 11, 13, 17, et la suite se poursuit indéfiniment.

Un nombre supérieur à 1 qui n'est pas premier est appelé un nombre composé, car il peut être décomposé en facteurs plus petits. Le nombre 9 est composé car il est divisible par 3, et 15 est composé car il est divisible par 3 et par 5.

À noter: 0 et 1 ne sont pas des nombres premiers. 2 est le seul nombre premier pair, et les valeurs négatives ne sont jamais considérées comme premières.

Comment vérifier si un nombre est premier ? Java

La stratégie de vérification consiste en un test de divisibilité simple. On prend la valeur candidate, on la divise successivement par chaque entier inférieur, et on examine le reste de l'opération modulo. Un reste nul prouve l'existence d'un diviseur, ce qui invalide immédiatement le nombre.

Logique du programme :

• Il faut diviser un nombre donné, par exemple 17, par les nombres compris entre 2 et 17 et vérifier le reste. Si le reste est 0, le nombre n'est pas premier.
• Aucun nombre n'est divisible par plus de la moitié de lui-même. Nous devons donc boucle à travers juste numberToCheck/2Si la valeur d'entrée est 17, la moitié est 8.5 et la boucle parcourra les valeurs de 2 à 8.
• Si le nombre à vérifier est entièrement divisible par un autre nombre, l'indicateur isPrime est défini sur false et la boucle est quittée.

Deux Java Les caractéristiques constituent l'intégralité de l'algorithme. L'opérateur modulo % renvoie le reste d'une division entière, et le break Cette instruction arrête la boucle dès que la réponse est connue, évitant ainsi l'exécution d'itérations inutiles.

Java Programme pour vérifier si un nombre est premier ou non

Le programme ci-dessous attribue la valeur 17 à la variable `numberToCheck` et affiche chaque étape de la division, vous permettant ainsi de suivre le raisonnement ligne par ligne. Le code est modifiable ; changez la valeur et exécutez-le à nouveau avec un nombre composé, par exemple 21, pour observer le résultat inverse.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

Production attendue:

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

La boucle s'arrête à 8 car 17 divisé par 2 est égal à 8 en arithmétique entière. Comme aucun reste n'a jamais été nul, l'indicateur `isPrime` conserve sa valeur initiale `true` et la condition finale affiche le résultat positif.

Vérification optimisée des nombres premiers à l'aide de la méthode de la racine carrée

Diviser jusqu'à la moitié du nombre est correct, mais inutile. Si un nombre n possède un diviseur supérieur à sa racine carrée, le codiviseur correspondant est nécessairement inférieur à la racine carrée ; il aurait donc déjà été trouvé. Vérifier jusqu'à √n permet par conséquent d'obtenir le même résultat en beaucoup moins d'itérations.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

Sortie :

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

La condition i * i <= n Cette méthode évite l'appel à la fonction Math.sqrt pour les nombres à virgule flottante, et le pas de 2 permet d'ignorer chaque diviseur pair. Pour une valeur comme 1 000 003, la boucle classique effectue environ 500 000 itérations, tandis que cette version en effectue moins de 500.

Vérifier si l'utilisateur a saisi un nombre premier

L'utilisation de données codées en dur est pratique pour les démonstrations, mais les exercices réels nécessitent généralement une saisie au clavier. La classe Scanner lit un entier depuis la console et le transmet à la méthode isPrime.

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

Exemple d'exécution :

Enter a number: 29
29 is a Prime number

Erreurs courantes lors de l'écriture d'un programme de nombres premiers

La plupart des erreurs lors de soumissions incorrectes surviennent au niveau des valeurs limites plutôt qu'au niveau de la boucle principale. La liste ci-dessous recense les erreurs les plus fréquentes dans les programmes de débutants.

1. Début de la boucle à 1 : Tout entier est divisible par 1, donc l'indicateur est immédiatement mis à faux et le programme signale qu'aucun nombre n'est premier.
2. Considérer 1 comme premier : La valeur 1 n'a qu'un seul diviseur, elle ne satisfait donc pas à la définition à deux diviseurs et doit renvoyer la valeur fausse.
3. En omettant l'instruction de rupture : Le programme renvoie toujours la bonne réponse, mais il continue d'itérer après que le verdict soit connu, ce qui entraîne une perte de temps pour les entrées volumineuses.
4. L'utilisation de i <= n comme la limite : Le nombre se divise toujours lui-même, la boucle doit donc s'arrêter avant d'atteindre n.
5. Comparer avec = au lieu de ==: Un simple signe égal assigne une valeur au lieu de la tester, ce qui produit une erreur de compilation dans la condition if.

Comparaison des méthodes de vérification de la primauté

Choisissez la méthode qui correspond à la taille de l'entrée et selon qu'une seule valeur ou une plage entière doit être testée.

Lorsqu'il s'agit de classer une plage de valeurs plutôt qu'une seule, le tamis est bien plus efficace. Notre programme associé permet de trouver Prime Numbers à partir de 1 100 illustre ce schéma. Pour des exercices similaires basés sur des boucles, consultez la section correspondante. la série de Fibonacci dans Java, le Java programme palindromeainsi que, Bubble Algorithme de tri dans JavaLes débutants qui souhaitent se rafraîchir la mémoire sur la déclaration du drapeau et le comptage devraient lire à ce sujet. Java les variables en général Java tutoriel.

FAQ