Vérifier si un nombre est premier en Java

1. Introduction

Tout d'abord, passons en revue une théorie de base.

En termes simples, un nombre est premier s'il n'est divisible que par un et par le nombre lui-même. Les nombres non premiers sont appelés nombres composés. Et le numéro un n'est ni premier ni composite.

Dans cet article, nous examinerons différentes manières de vérifier la primalité d'un nombre en Java.

2. Une implémentation personnalisée

Avec cette approche, nous pouvons vérifier si un nombre entre 2 et (racine carrée du nombre) peut diviser avec précision le nombre.

La logique suivante retournera vrai si le nombre est premier:

public boolean isPrime(int number) { return number > 1 && IntStream.rangeClosed(2, (int) Math.sqrt(number)) .noneMatch(n -> (number % n == 0)); }

3. Utilisation de BigInteger

La classe BigInteger est généralement utilisée pour stocker des entiers de grande taille, c'est-à-dire ceux supérieurs à 64 bits. Il fournit quelques API utiles pour travailler avec des valeurs int et longues .

L'une de ces API est isProbablePrime . Cette API renvoie false si le nombre est définitivement un composite et renvoie true s'il y a une certaine probabilité qu'il soit premier. Il est utile lorsqu'il s'agit de grands entiers car cela peut être un calcul assez intensif pour les vérifier complètement.

Petite remarque : l' API isProbablePrime utilise ce qu'on appelle les tests de primalité «Miller - Rabin et Lucas - Lehmer» pour vérifier si le nombre est probablement premier. Dans les cas où le nombre est inférieur à 100 bits, seul le test «Miller - Rabin» est utilisé, sinon, les deux tests sont utilisés pour vérifier la primalité d'un nombre.

Le test "Miller-Rabin" itère un nombre fixe de fois pour déterminer la primalité du nombre et ce nombre d'itérations est déterminé par un simple contrôle qui implique la longueur en bits du nombre et la valeur de certitude passée à l'API:

public boolean isPrime(int number) { BigInteger bigInt = BigInteger.valueOf(number); return bigInt.isProbablePrime(100); }

4. Utilisation d'Apache Commons Math

Apache Commons Math API fournit une méthode nommée org.apache.commons.math3.primes.Primes, que nous utiliserons pour vérifier la primalité d'un nombre.

Tout d'abord, nous devons importer la bibliothèque Apache Commons Math en ajoutant la dépendance suivante dans notre pom.xml :

 org.apache.commons commons-math3 3.6.1 

La dernière version de commons-math3 peut être trouvée ici.

Nous pourrions faire la vérification en appelant simplement la méthode:

Primes.isPrime(number);

5. Conclusion

Dans cet article rapide, nous avons vu trois façons de vérifier la primalité du nombre.

Le code pour cela se trouve dans le package com.baeldung.algorithms.primechecker sur Github.