Java >> Tutoriel Java >  >> Java

Programme de nombres premiers en Java

Dans cet article, nous développerons un programme de nombres premiers en Java, un programme pour vérifier le nombre premier en Java et un programme Java pour imprimer des nombres premiers entre deux nombres.

Un nombre naturel qui n'a que deux facteurs (1 et lui-même) est appelé un nombre premier. Par exemple, 5 est un nombre premier car il n'a que deux facteurs 1 et 5. De même, 9 n'est pas un nombre premier car il a plus de 2 facteurs qui sont 1, 3 et 9.

Programme de nombres premiers simples en Java

Développer un programme pour vérifier que le nombre donné est un nombre premier ou non en java; Tout d'abord, vous devez savoir comment développer un programme Java pour connaître tous les facteurs d'un nombre. Parce que si un nombre a plus de 2 facteurs alors seulement, c'est un nombre premier. Tous les nombres négatifs, 0 et 1 ne sont pas des nombres premiers.

Programme de nombres premiers en Java utilisant la boucle for

import java.util.Scanner;

public class SimplePrimeNoProgram {

  public static boolean isPrime(int number){

    // All negative numbers, 0 and 1 
    // are not a prime number
    if(number<=1) return false;

    // check for remaining
    for(int i=2; i<number; i++)
        if(number%i == 0) 
            return false;

    return true;
  }

  public static void main(String[] args) {

    // declare variables
    int number = 0;
    boolean flag = false;

    // create Scanner class object
    Scanner scan = new Scanner(System.in);

    // read number
    System.out.print("Enter a number:: ");
    number = scan.nextInt();

    // check number is prime number or not
    flag  = isPrime(number);

    // display result
    if(flag) // true
       System.out.println(number+
                " is a prime number");
    else 
       System.out.println(number+
                " is not a prime number");

    // close Scanner class object
    scan.close();
  }
}

Sortie pour différents cas de test :-

Entrer un nombre ::11
11 est un nombre premier

Entrez un nombre ::9
9 n'est pas un nombre premier

La complexité temporelle de cette solution est O(n) .

Voir également :- Numéro spécial, Numéro magique, Numéro Armstrong, Numéro parfait, Numéro maléfique, Numéro espion, Numéro ensoleillé en Java

Utiliser la boucle while

Le précédent programme de nombres premiers en Java a été développé en utilisant la boucle for, mais nous pouvons également utiliser une boucle while au lieu de la boucle for. Utilisez la méthode ci-dessous dans le programme précédent.

Méthode des nombres premiers en Java utilisant la boucle while

public static boolean isPrime(int number) {

   // declare variables
   int i = 2;

   // negative numbers, 0 and 1 
   // are not a prime number
   if(number<=1) return false;

   // loop to repeat the process
   while(i<number) {
       if(number%i == 0) 
           return false;
       i++;
   }

   return true;
}

La complexité temporelle de cette solution est O(n) .

Programme pour vérifier les nombres premiers en Java

Les programmes ci-dessus sont corrects et donnent une sortie correcte mais ils donnent moins de performances, leur complexité temporelle était O(n). Nous pouvons optimiser les programmes ci-dessus.

Il y a certains points que nous devons garder à l'esprit pour développer le meilleur programme principal en Java qui offrira des performances élevées.

  • Tous les nombres négatifs, 0 et 1 ne sont pas des nombres premiers.
  • 2 est le seul nombre premier pair.
  • Tous les nombres premiers (sauf 2 et 3) peuvent être présentés sous la forme 6n+1 ou 6n-1
  • 2 et 3 sont les deux seuls nombres naturels consécutifs qui sont aussi premiers.

Nous pouvons faire les optimisations suivantes,

1) Au lieu de vérifier jusqu'à i=1 au nombre, nous ne devrions vérifier que jusqu'à √n.

Dans le post trouver des facteurs en java, nous avons appris que nous pouvons utiliser le sqrt() méthode pour limiter l'itération et divisez le nombre par la variable d'itérateur pour trouver les facteurs qui sont supérieurs à la valeur de la racine carrée du nombre. Le code peut être écrit comme,

for(….; i<=Math.sqrt(number); ….) {
      // logic
}

2) Tous les nombres premiers sauf 2 et 3 sont sous la forme de 6k ± 1. Voir :- Test de primalité

Puisque tous les entiers peuvent être exprimés par (6k+i) pour un entier k et pour i=-1,0,1,2,3 ou 4 (ici 5 s'écrit -1). Étant donné que les nombres entiers représentés par 6k + 0, 6k + 2 et 6k + 4 sont des nombres pairs et divisibles par deux, ils ne peuvent donc pas être un nombre premier. Les nombres entiers représentés par 6k + 3 seront divisibles par 3, il ne peut donc pas non plus s'agir d'un nombre premier. Maintenant, les nombres entiers restants qui sont représentés par 6k+1 et 6k-1 peuvent être un nombre premier ou un nombre composé. Nous devons donc vérifier uniquement les nombres représentés par 6k ± 1.

Par conséquent, il est préférable de vérifier que le nombre est divisible par 2 ou 3, si oui, alors ce n'est pas un nombre premier.

if(number%2==0 || number%3==0) 
return false;

La logique des nombres premiers

Code de méthode Java pour vérifier que le nombre donné est un nombre premier ou non

public static boolean isPrime(int number) {

  // negative numbers, 0 and 1 are 
  // not a prime number
  if( number <= 1 ) return false;

  // 2 and 3 are prime numbers
  if( number <= 3 ) return true;

  // numbers divisible by 2 and 3
  // are not prime number
  if(number%2==0 || number%3==0)
      return false;

  // logic for remaining numbers
  for(int i=5; i<=Math.sqrt(number); i=i+6) {

      // 6k+1 => number%i
      // 6k-1 => number % (i+2)
      if(number%i == 0 || number%(i+2) == 0) 
          return false;
  }

  // if all above conditions are not satisfied
  return true;
}

La complexité temporelle de cette méthode est O(√n) .

Programme Java

Dans le checkPrime() nous avons utilisé la boucle for pour vérifier le nombre premier en java, mais nous pouvons également utiliser une boucle while ou do-while. Maintenant, sur la base de cette méthode, nous allons développer un programme de nombres premiers en Java en utilisant le Scanner.

import java.util.Scanner;

public class PrimeNumber {

  public static boolean isPrime(int number){

     // negative numbers, 0 and 1 are 
     // not a prime number
     if( number <= 1 ) return false;

     // 2 and 3 are prime numbers
     if( number <= 3 ) return true;

     // numbers divisible by 2 and 3
     // are not prime number
     if(number%2==0 || number%3==0)
         return false;

     // logic for remaining numbers
     for(int i=5; i<=Math.sqrt(number); i=i+6){
        if(number%i == 0 || number%(i+2) == 0) 
            return false;
     }

     return true;
  }

  public static void main(String[] args) {

      // declare variables
      int number = 0;
      boolean isPrime = false;

      // create Scanner class object
      Scanner scan = new Scanner(System.in);

      // read number
      System.out.print("Enter a number:: ");
      number = scan.nextInt();

      // check number is prime number or not
      isPrime = isPrime(number);

      // display result
      if(isPrime) // true
         System.out.println(number+
                  " is a prime number");
      else 
         System.out.println(number+
                  " is not a prime number");

      // close Scanner class object
      scan.close();
  }
}

Sortie :-

Entrer un nombre ::11
11 est un nombre premier

Entrez un nombre ::9
9 n'est pas un nombre premier

La complexité temporelle de cette solution est O(√n) .

Le nombre premier utilisant la récursivité en Java

import java.util.Scanner;

public class PrimeNumber {

  public static boolean isPrime(int number, int i){

     // negative numbers, 0 and 1 are 
     // not a prime number
     if( number <= 2 )
       return (number != 2) ? false : true;

     if( number % i == 0 ) return false;
     if( i*i > number ) return true;

     // check for the next
     return isPrime(number, i+1);
  }

  public static void main(String[] args) {

      // declare variables
      int number = 0;
      boolean flag = false;

      // create Scanner class object
      Scanner scan = new Scanner(System.in);

      // read number
      System.out.print("Enter a number:: ");
      number = scan.nextInt();

      // check number is prime number or not
      flag = isPrime(number, 2);

      // display result
      if(flag) // true
          System.out.println(number+
                  " is a prime number");
      else 
          System.out.println(number+
                   " is not a prime number");

      // close Scanner class object
      scan.close();
   }
}

Programme pour imprimer les 10 premiers nombres premiers en Java

public class PrintPrimeNumber {

  public static boolean isPrime(int number) {

    /* Negative numbers, 0 and 1 
    * are not a prime number
    * 
    * Even numbers (except 2) are
    * also not a prime number
    */
    if(number == 2) return true;
    else if(number<=1 || number%2==0)
         return false;

    // logic for remaining numbers
    for(int i=3; i<=Math.sqrt(number); i++){
         if(number%i == 0) return false;
    }

    return true;
  }

  public static void main(String[] args) {

    System.out.println(
      "First 10 prime numbers in Java are::");

    // variables
    int i=1, count=0;

    // loop to repeat the process
    while(count<10) {
       if(isPrime(i)) {
          System.out.print( i + " ");
          count++;
       }
       i++;
    }
  }
}

Sortie :-

Les 10 premiers nombres premiers en Java sont : :
2 3 5 7 11 13 17 19 23 29

Programme Java pour imprimer des nombres premiers entre deux nombres donnés

Le programme précédent imprime les 10 premiers nombres premiers en Java. Semblable à ce programme, nous pouvons écrire un programme pour imprimer des nombres premiers entre deux nombres par exemple :- programme pour imprimer des nombres premiers de 1 à 100 en java.

import java.util.Scanner;

public class PrimeNumberInRange {

  public static boolean isPrime(int number) {

    /* Negative numbers, 0 and 1 
     * are not a prime number
     * 
     * Even numbers (except 2) are
     * also not a prime number
     */
     if(number == 2) return true;
     else if(number<=1 || number%2==0)
         return false;

     // logic for remaining numbers
     for(int i=3; i<=Math.sqrt(number); i++) {
         if(number%i == 0) return false;
     }

     return true;
  }

  public static void main(String[] args) {

     // declare variables
     int minRange , maxRange;

     // create Scanner class object
     Scanner scan = new Scanner(System.in);

     // read inputs
     System.out.print("Enter min Range value::");
     minRange = scan.nextInt();
     System.out.print("Enter max Range value::");
     maxRange = scan.nextInt();

     // check in range
     System.out.println("Prime numbers from "+
              minRange+" to "+maxRange+" :: ");
     for(int i = minRange; i<= maxRange; i++)
        if(isPrime(i)) 
           System.out.print( i + " ");

     // close Scanner class object
     scan.close();
  }
}

La sortie pour différents cas de test est :-

Entrez la valeur de la plage min : 1
Entrez la valeur de la plage max : 100
Nombres premiers de 1 à 100 : :
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Entrez la valeur de plage min : 100
Entrez la valeur de plage max : 200
Nombres premiers de 100 à 200 : :
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199


Balise Java