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