Générer des nombres premiers en Java

1. Introduction

Dans ce didacticiel, nous montrerons différentes manières de générer des nombres premiers à l'aide de Java.

Si vous cherchez à vérifier si un nombre est premier, voici un guide rapide sur la façon de procéder.

2. Nombres premiers

Commençons par la définition de base. Un nombre premier est un entier naturel supérieur à un qui n'a pas de diviseur positif autre que un et lui-même.

Par exemple, 7 est premier car 1 et 7 sont ses seuls facteurs entiers positifs, alors que 12 ne l'est pas car il a les diviseurs 3 et 2 en plus de 1, 4 et 6.

3. Génération de nombres premiers

Dans cette section, nous verrons comment nous pouvons générer efficacement des nombres premiers inférieurs à une valeur donnée.

3.1. Java 7 et avant - Brute Force

public static List primeNumbersBruteForce(int n) { List primeNumbers = new LinkedList(); for (int i = 2; i <= n; i++) { if (isPrimeBruteForce(i)) { primeNumbers.add(i); } } return primeNumbers; } public static boolean isPrimeBruteForce(int number) { for (int i = 2; i < number; i++) { if (number % i == 0) { return false; } } return true; } 

Comme vous pouvez le voir, primeNumbersBruteForce itère sur les nombres de 2 à n et appelle simplement la méthode isPrimeBruteForce () pour vérifier si un nombre est premier ou non.

La méthode vérifie la divisibilité de chaque nombre par les nombres dans une plage de 2 au nombre-1 .

Si à un moment donné nous rencontrons un nombre divisible, nous retournons false. À la fin, lorsque nous constatons que ce nombre n'est divisible par aucun de ses nombres précédents, nous retournons true indiquant que c'est un nombre premier.

3.2. Efficacité et optimisation

L'algorithme précédent n'est pas linéaire et a la complexité temporelle de O (n ^ 2). L'algorithme n'est pas non plus efficace et il y a clairement une marge d'amélioration.

Regardons la condition dans la méthode isPrimeBruteForce () .

Lorsqu'un nombre n'est pas un nombre premier, ce nombre peut être factorisé en deux facteurs à savoir a et b ie nombre = a * b. Si a et b étaient tous deux supérieurs à la racine carrée de n , a * b serait supérieur à n .

Donc au moins un de ces facteurs doit être inférieur ou égal à la racine carrée d'un nombre et pour vérifier si un nombre est premier, il suffit de tester les facteurs inférieurs ou égaux à la racine carrée du nombre à vérifier.

Les nombres premiers ne peuvent jamais être un nombre pair car les nombres pairs sont tous divisibles par 2.

De plus, les nombres premiers ne peuvent jamais être un nombre pair car les nombres pairs sont tous divisibles par 2.

En gardant à l'esprit les idées ci-dessus, améliorons l'algorithme:

public static List primeNumbersBruteForce(int n) { List primeNumbers = new LinkedList(); if (n >= 2) { primeNumbers.add(2); } for (int i = 3; i <= n; i += 2) { if (isPrimeBruteForce(i)) { primeNumbers.add(i); } } return primeNumbers; } private static boolean isPrimeBruteForce(int number) { for (int i = 2; i*i < number; i++) { if (number % i == 0) { return false; } } return true; } 

3.3. Utilisation de Java 8

Voyons comment nous pouvons réécrire la solution précédente en utilisant des idiomes Java 8:

public static List primeNumbersTill(int n) { return IntStream.rangeClosed(2, n) .filter(x -> isPrime(x)).boxed() .collect(Collectors.toList()); } private static boolean isPrime(int number) { return IntStream.rangeClosed(2, (int) (Math.sqrt(number))) .filter(n -> (n & 0X1) != 0) .allMatch(n -> x % n != 0); } 

3.4. Utilisation du tamis d'Ératosthène

Il existe encore une autre méthode efficace qui pourrait nous aider à générer efficacement des nombres premiers, et elle s'appelle Sieve Of Eratosthenes. Son efficacité en temps est O (n logn).

Jetons un coup d'œil aux étapes de cet algorithme:

  1. Créez une liste d'entiers consécutifs de 2 à n : (2, 3, 4,…, n)
  2. Initialement, soit p égal à 2, le premier nombre premier
  3. À partir de p , comptez par incréments de p et marquez chacun de ces nombres supérieurs à p lui-même dans la liste. Ces nombres seront 2p, 3p, 4p, etc .; notez que certains d'entre eux ont peut-être déjà été marqués
  4. Trouvez le premier nombre supérieur à p dans la liste qui n'est pas marqué. S'il n'y avait pas un tel numéro, arrêtez. Sinon, laissez p maintenant égaler ce nombre (qui est le prochain premier), et répétez à partir de l'étape 3

À la fin, lorsque l'algorithme se termine, tous les nombres de la liste qui ne sont pas marqués sont les nombres premiers.

Voici à quoi ressemble le code:

public static List sieveOfEratosthenes(int n) { boolean prime[] = new boolean[n + 1]; Arrays.fill(prime, true); for (int p = 2; p * p <= n; p++) { if (prime[p]) { for (int i = p * 2; i <= n; i += p) { prime[i] = false; } } } List primeNumbers = new LinkedList(); for (int i = 2; i <= n; i++) { if (prime[i]) { primeNumbers.add(i); } } return primeNumbers; } 

3.5. Exemple de travail de tamis d'Eratosthène

Voyons comment cela fonctionne pour n = 30.

Considérez l'image ci-dessus, voici les passes effectuées par l'algorithme:

  1. La boucle commence par 2, donc nous laissons 2 non marqués et marquons tous les diviseurs de 2. Il est marqué dans l'image avec la couleur rouge
  2. La boucle passe à 3, donc nous laissons 3 non marqués et marquons tous les diviseurs de 3 non déjà marqués. Il est marqué dans l'image avec la couleur verte
  3. La boucle passe à 4, c'est déjà marqué, donc on continue
  4. La boucle passe à 5, donc nous laissons 5 non marqués et marquons tous les diviseurs de 5 non déjà marqués. Il est marqué dans l'image avec la couleur violette
  5. Nous continuons les étapes ci-dessus jusqu'à ce que la boucle soit atteinte égale à la racine carrée de n

4. Conclusion

Dans ce didacticiel rapide, nous avons illustré des façons dont nous pouvons générer des nombres premiers jusqu'à la valeur «N».

L'implémentation de ces exemples est disponible à l'adresse over sur GitHub.