Generiranje prostih brojeva u Javi

1. Uvod

U ovom uputstvu pokazat ćemo razne načine na koje možemo generirati proste brojeve pomoću Jave.

Ako želite provjeriti je li broj prost - evo kratkog vodiča kako to učiniti.

2. Prosti brojevi

Počnimo s osnovnom definicijom. Prosti broj je prirodni broj veći od broja koji nema pozitivnih djelitelja osim jednog i samoga sebe.

Na primjer, 7 je prosto jer su mu 1 i 7 jedini pozitivni cjelobrojni čimbenici, dok 12 nije zato što uz 1, 4 i 6 ima djelitelje 3 i 2.

3. Generiranje prostih brojeva

U ovom ćemo odjeljku vidjeti kako možemo učinkovito generirati proste brojeve koji su niži od zadane vrijednosti.

3.1. Java 7 i prije - Brute Force

javni statički popis primeNumbersBruteForce (int n) {Lista primeNumbers = novi LinkedList (); za (int i = 2; i <= n; i ++) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} return primeNumbers; } javna statička logička vrijednost jePrimeBruteForce (int broj) {for (int i = 2; i <broj; i ++) {if (broj% i == 0) {return false; }} return true; } 

Kao što vidiš, primeNumbersBruteForce je ponavljanje brojeva od 2 do n i jednostavno pozivanje isPrimeBruteForce () metoda za provjeru je li broj prost ili nije.

Metoda provjerava djeljivost svakog broja brojevima u rasponu od 2 do broj 1.

Ako u bilo kojem trenutku naiđemo na broj koji je djeljiv, vratit ćemo false. Na kraju kada utvrdimo da taj broj nije djeljiv ni sa jednim prethodnim brojem, vraćamo true označavajući njegov prost broj.

3.2. Učinkovitost i optimizacija

Prethodni algoritam nije linearan i ima vremensku složenost O (n ^ 2). Algoritam također nije učinkovit i očito postoji prostor za poboljšanje.

Pogledajmo stanje u isPrimeBruteForce () metoda.

Kada broj nije prost, taj se broj može podijeliti na dva čimbenika a i b tj. broj = a * b. Ako oboje a i b bili veći od kvadratnog korijena od n, a * b bio bi veći od n.

Dakle, barem jedan od tih čimbenika mora biti manji od kvadratnog korijena broja ili jednak njemu, a da bismo provjerili je li broj prost, trebamo testirati samo faktore manje ili jednake kvadratnom korijenu broja koji se provjerava.

Prosti brojevi nikada ne mogu biti paran broj, jer su svi parni brojevi djeljivi sa 2.

Uz to, prosti brojevi nikada ne mogu biti paran broj jer su svi parni brojevi djeljivi sa 2.

Imajući na umu gornje ideje, unaprijedimo algoritam:

javni statički popis primeNumbersBruteForce (int n) {Lista primeNumbers = novi LinkedList (); if (n> = 2) {primeNumbers.add (2); } za (int i = 3; i <= n; i + = 2) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} return primeNumbers; } privatni statički logički isPrimeBruteForce (int broj) {for (int i = 2; i * i <broj; i ++) {if (broj% i == 0) {return false; }} return true; } 

3.3. Korištenje Jave 8

Pogledajmo kako možemo prepisati prethodno rješenje pomoću Java 8 idioma:

javni statički popis primeNumbersTill (int n) {return IntStream.rangeClosed (2, n) .filter (x -> isPrime (x)). boxed () .collect (Collectors.toList ()); } privatni statički logički isPrime (int broj) {return IntStream.rangeClosed (2, (int) (Math.sqrt (broj))) .filter (n -> (n & 0X1)! = 0) .allMatch (n -> x% n! = 0); } 

3.4. Korištenje sita Eratostena

Postoji još jedna učinkovita metoda koja bi nam mogla pomoći da učinkovito generiramo proste brojeve, a zove se Sieve Of Eratosthenes. Njegova vremenska učinkovitost je O (n logn).

Pogledajmo korake ovog algoritma:

  1. Stvorite popis uzastopnih cijelih brojeva od 2 do n: (2, 3, 4,…, n)
  2. U početku neka str biti jednak 2, prvi prost broj
  3. Počevši od str, odbrojavajte u koracima od str i svaki od ovih brojeva označite većim od str sebe na popisu. Ti će brojevi biti 2p, 3p, 4p itd .; imajte na umu da su neki od njih možda već označeni
  4. Pronađite prvi broj veći od str na popisu koji nije označen. Ako nije bilo tog broja, zaustavite se. Inače, neka str sada izjednačite ovaj broj (koji je sljedeći prosti broj) i ponovite od koraka 3

Na kraju kada se algoritam završi, svi brojevi na popisu koji nisu označeni primarni su brojevi.

Evo kako kod izgleda:

javni statički popis sieveOfEratosthenes (int n) {boolean prime [] = new boolean [n + 1]; Nizovi.fill (osnovno, istinito); for (int p = 2; p * p <= n; p ++) {if (prime [p]) {for (int i = p * 2; i <= n; i + = p) {prime [i] = lažno; }}} Popis primarnih brojeva = novi LinkedList (); for (int i = 2; i <= n; i ++) {if (prime [i]) {primeNumbers.add (i); }} return primeNumbers; } 

3.5. Radni primjer sita Eratostena

Pogledajmo kako to radi za n = 30.

Uzmite u obzir gornju sliku, evo prolaza koje je izvršio algoritam:

  1. Petlja započinje s 2, tako da 2 ostavljamo neoznačena i označavamo sve djelitelje 2. Na slici je označena crvenom bojom
  2. Petlja se pomiče na 3, pa ostavljamo 3 neoznačena i označavamo sve djelitelje 3 koji još nisu označeni. Na slici je označen zelenom bojom
  3. Petlja se pomiče na 4, već je označena, pa nastavljamo
  4. Petlja se pomiče na 5, tako da 5 ostavljamo neoznačeno i označavamo sve djelitelje 5 koji još nisu označeni. Na slici je označen ljubičastom bojom
  5. Nastavljamo iznad koraka dok se petlja ne postigne jednaka kvadratnom korijenu od n

4. Zaključak

U ovom smo brzom vodiču ilustrirali načine na koje možemo generirati proste brojeve do vrijednosti 'N'.

Implementacija ovih primjera može se naći na GitHubu.