Priemgetallen genereren in Java

1. Inleiding

In deze tutorial laten we verschillende manieren zien waarop we priemgetallen kunnen genereren met Java.

Als u wilt controleren of een getal een priemgetal is, vindt u hier een korte handleiding over hoe u dat moet doen.

2. Priemgetallen

Laten we beginnen met de kerndefinitie. Een priemgetal is een natuurlijk getal dat groter is dan één dat geen andere positieve delers heeft dan één en zichzelf.

7 is bijvoorbeeld een priemgetal omdat 1 en 7 de enige positieve integerfactoren zijn, terwijl 12 niet is omdat het naast 1, 4 en 6 de delers 3 en 2 heeft.

3. Priemgetallen genereren

In dit gedeelte zullen we zien hoe we efficiënt priemgetallen kunnen genereren die lager zijn dan een bepaalde waarde.

3.1. Java 7 en eerder - Brute Force

openbare statische lijst primeNumbersBruteForce (int n) {lijst primeNumbers = nieuwe LinkedList (); for (int i = 2; i <= n; i ++) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} retourneer priemgetallen; } openbare statische boolean isPrimeBruteForce (int nummer) {voor (int i = 2; i <nummer; i ++) {if (nummer% i == 0) {return false; }} retourneren waar; } 

Zoals je kunt zien, primeNumbersBruteForce itereert over de getallen van 2 tot n en gewoon de isPrimeBruteForce () methode om te controleren of een getal een priemgetal is of niet.

De methode controleert de deelbaarheid van elk nummer door de nummers in een bereik van 2 tot nummer 1.

Als we op enig moment een getal tegenkomen dat deelbaar is, retourneren we false. Als we aan het einde ontdekken dat dat getal niet deelbaar is door een van het voorgaande getal, geven we true terug, wat aangeeft dat het een priemgetal is.

3.2. Efficiëntie en optimalisatie

Het vorige algoritme is niet lineair en heeft de tijdcomplexiteit van O (n ^ 2). Het algoritme is ook niet efficiënt en er is duidelijk ruimte voor verbetering.

Laten we eens kijken naar de toestand in het isPrimeBruteForce () methode.

Wanneer een getal geen priemgetal is, kan dit getal in twee factoren worden verdisconteerd, namelijk een en b d.w.z. aantal = a * b. Als beide een en b waren groter dan de vierkantswortel van n, een * b zou groter zijn dan n.

Dus minstens één van die factoren moet kleiner zijn dan of gelijk zijn aan de vierkantswortel van een getal en om te controleren of een getal een priemgetal is, hoeven we alleen te testen op factoren die lager zijn dan of gelijk zijn aan de vierkantswortel van het getal dat wordt gecontroleerd.

Priemgetallen kunnen nooit een even getal zijn, aangezien even getallen allemaal deelbaar zijn door 2.

Bovendien kunnen priemgetallen nooit een even getal zijn, omdat even getallen allemaal deelbaar zijn door 2.

Laten we, rekening houdend met bovenstaande ideeën, het algoritme verbeteren:

openbare statische lijst primeNumbersBruteForce (int n) {lijst primeNumbers = nieuwe LinkedList (); if (n> = 2) {priemgetallen.add (2); } for (int i = 3; i <= n; i + = 2) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} retourneer priemgetallen; } privé statische boolean isPrimeBruteForce (int nummer) {voor (int i = 2; i * i <nummer; i ++) {if (nummer% i == 0) {return false; }} retourneren waar; } 

3.3. Java 8 gebruiken

Laten we eens kijken hoe we de vorige oplossing kunnen herschrijven met behulp van Java 8-idiomen:

openbare statische lijst primeNumbersTill (int n) {retourneer 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. Zeef van Eratosthenes gebruiken

Er is nog een andere efficiënte methode die ons zou kunnen helpen om priemgetallen efficiënt te genereren, en deze heet Sieve Of Eratosthenes. Zijn tijdsefficiëntie is O (n logn).

Laten we de stappen van dit algoritme eens bekijken:

  1. Maak een lijst met opeenvolgende gehele getallen van 2 tot n: (2, 3, 4, ..., n)
  2. In eerste instantie, laat p gelijk zijn aan 2, het eerste priemgetal
  3. Beginnend vanaf p, tel op in stappen van p en markeer elk van deze getallen groter dan p zelf in de lijst. Deze nummers zijn 2p, 3p, 4p, enz .; Houd er rekening mee dat sommige ervan mogelijk al zijn gemarkeerd
  4. Zoek het eerste getal groter dan p in de lijst die niet is gemarkeerd. Als er niet zo'n nummer was, stop dan. Anders, laat p nu gelijk aan dit nummer (dat het volgende priemgetal is), en herhaal vanaf stap 3

Aan het einde wanneer het algoritme eindigt, zijn alle nummers in de lijst die niet zijn gemarkeerd de priemgetallen.

Hier is hoe de code eruit ziet:

openbare statische lijst sieveOfEratosthenes (int n) {boolean prime [] = nieuwe 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] = vals; }}} Lijst primeNumbers = nieuwe LinkedList (); for (int i = 2; i <= n; i ++) {if (prime [i]) {primeNumbers.add (i); }} retourneer priemgetallen; } 

3.5. Werkvoorbeeld van zeef van Eratosthenes

Laten we eens kijken hoe het werkt voor n = 30.

Beschouw de bovenstaande afbeelding, hier zijn de passen die door het algoritme zijn gemaakt:

  1. De lus begint met 2, dus laten we 2 ongemarkeerd en markeren alle delers van 2. Het is in de afbeelding gemarkeerd met de rode kleur
  2. De lus gaat naar 3, dus laten we 3 ongemarkeerd en markeren we alle delers van 3 die nog niet zijn gemarkeerd. Het is in afbeelding gemarkeerd met de groene kleur
  3. Loop gaat naar 4, het is al gemarkeerd, dus we gaan verder
  4. Loop gaat naar 5, dus laten we 5 ongemarkeerd en markeren alle delers van 5 die nog niet zijn gemarkeerd. Het is in afbeelding gemarkeerd met de paarse kleur
  5. We gaan door met bovenstaande stappen totdat de lus is bereikt die gelijk is aan de vierkantswortel van n

4. Conclusie

In deze korte tutorial hebben we manieren geïllustreerd waarop we priemgetallen kunnen genereren tot 'N'-waarde.

De implementatie van deze voorbeelden is te vinden op GitHub.