streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban bemutatjuk a Java segítségével a prímszámok előállításának különböző módjait.

Ha azt szeretné ellenőrizni, hogy egy szám elsődleges-e - itt van egy rövid útmutató, hogyan kell ezt megtenni.

2. Prímszámok

Kezdjük az alapdefinícióval. A prímszám egy olyan természetes szám, amely nagyobb, mint az a szám, amelynek nincs pozitív osztója, csak egy és maga.

Például a 7 azért elsődleges, mert 1 és 7 az egyetlen pozitív egész tényező, míg a 12 nem azért, mert az 1, 4 és 6 mellett 3 és 2 osztókkal rendelkezik.

3. Prímszámok generálása

Ebben a szakaszban meglátjuk, hogyan lehet hatékonyan előállítani egy adott értéknél alacsonyabb prímszámokat.

3.1. Java 7 és előtte - Brute Force

public static List primeNumbersBruteForce (int n) {List primeNumbers = új LinkedList (); mert (int i = 2; i <= n; i ++) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} return primeNumbers; } public static boolean isPrimeBruteForce (int szám) {for (int i = 2; i <szám; i ++) {if (szám% i == 0) {return false; }} return true; } 

Amint látod, primeNumbersBruteForce a 2-től a számokig iterál n és egyszerűen felhívja a isPrimeBruteForce () módszer annak ellenőrzésére, hogy egy szám prím-e vagy sem.

A módszer ellenőrzi az egyes számok oszthatóságát a 2 és a közötti tartományban lévő számokkal szám-1.

Ha valamikor osztható számmal találkozunk, akkor hamis értéket adunk vissza. A végén, amikor azt találjuk, hogy ez a szám nem osztható semmilyen korábbi számmal, akkor igaz értéket adunk vissza, jelezve a prímszámát.

3.2. Hatékonyság és optimalizálás

Az előző algoritmus nem lineáris, és időbeli összetettsége O (n ^ 2). Az algoritmus szintén nem hatékony, és egyértelműen van hová fejlődni.

Nézzük meg az állapotot a isPrimeBruteForce () módszer.

Ha egy szám nem prím, ezt a számot két tényezőre lehet felosztani, nevezetesen a és b azaz szám = a * b. Ha mindkettő a és b nagyobbak voltak, mint a négyzetgyök n, a * b nagyobb lenne, mint n.

Tehát e tényezők közül legalább egynek kisebbnek vagy egyenlőnek kell lennie egy szám négyzetgyökéhez, és annak ellenőrzéséhez, hogy egy szám elsőbb-e, csak az ellenőrizendő szám négyzetgyökével egyenlő vagy annál kisebb tényezőket kell tesztelnünk.

A prímszámok soha nem lehetnek párosak, mivel a páros számok mind oszthatók 2-vel.

Ezenkívül a prímszámok soha nem lehetnek páros számok, mivel a páros számok mind oszthatók 2-vel.

A fenti ötleteket szem előtt tartva fejlesszük az algoritmust:

public static List primeNumbersBruteForce (int n) {List primeNumbers = új LinkedList (); if (n> = 2) {prímszámok.add (2); } for (int i = 3; i <= n; i + = 2) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} return primeNumbers; } privát statikus logikai isPrimeBruteForce (int szám) {for (int i = 2; i * i <szám; i ++) {if (szám% i == 0) {return false; }} return true; } 

3.3. Java 8 használata

Nézzük meg, hogyan írhatjuk át az előző megoldást a Java 8 idiómák használatával:

public static List primeNumbersTill (int n) {return IntStream.rangeClosed (2, n) .filter (x -> isPrime (x)). boxed () .collect (Collectors.toList ()); } privát statikus logikai isPrime (int szám) {return IntStream.rangeClosed (2, (int) (Math.sqrt (szám))).. szűrő (n -> (n & 0X1)! = 0) .allMatch (n -> x% n! = 0); } 

3.4. Eratosthenes szitájának felhasználásával

Van még egy hatékony módszer, amely segíthet nekünk a prímszámok hatékony előállításában, és az úgynevezett Sieve Of Eratosthenes. Időhatékonysága O (n logn).

Vessünk egy pillantást az algoritmus lépéseire:

1. Hozzon létre egy listát az egymást követő egész számoktól 2-ig n: (2, 3, 4,…, n)
2. Kezdetben hagyd o legyen egyenlő 2, az első prímszám
3. Kezdve o, számolja fel o és mindegyik számot jelölje nagyobbnak, mint o magát a listán. Ezek a számok 2p, 3p, 4p stb. Lesznek; vegye figyelembe, hogy némelyiket lehet, hogy már megjelölték
4. Keresse meg az első számot, amely nagyobb, mint o a nem jelölt listában. Ha nem volt ilyen szám, hagyja abba. Egyébként hagyd o most megegyezik ezzel a számmal (ami a következő prím), és ismételje meg a 3. lépéstől

Az algoritmus lejártakor a lista minden olyan száma, amely nincs megjelölve, a prímszám.

Így néz ki a kód:

public static List szitaOfEratosthenes (int n) {logikai prím [] = új logikai [n + 1]; Tömbök.kitöltés (elsődleges, igaz); for (int p = 2; p * p <= n; p ++) {if (prím [p]) {for (int i = p * 2; i <= n; i + = p) {prím [i] = hamis; }}} List primeNumbers = új LinkedList (); mert (int i = 2; i <= n; i ++) {if (prím [i]) {prímszámokadd (i); }} return primeNumbers; } 

3.5. Működési példa az eratosthenes szitára

Lássuk, hogyan működik n = 30 esetén.

Tekintsük a fenti képet, itt vannak az algoritmus által leadott átadások:

1. A hurok 2-vel kezdődik, így 2-t jelölés nélkül hagyjuk, és a 2 összes osztóját megjelöljük. A kép piros színnel van jelölve.
2. A hurok 3-ra mozog, így 3-at jelöletlenül hagyunk, és 3-an még nem jelölt osztókat jelölünk. Képen zöld színnel van jelölve
3. A hurok 4-re lép, ez már meg van jelölve, így folytatjuk
4. A hurok 5-re mozog, így 5-öt jelölés nélkül hagyunk, és 5-ös összes osztóját megjelöljük még nem jelöltként. Képen lila színnel van jelölve
5. A fenti lépéseket addig folytatjuk, amíg a ciklus el nem éri a n

4. Következtetés

Ebben a gyors bemutatóban szemléltettük, hogy miként generálhatunk prímszámokat „N” értékig.

Ezeknek a példáknak a megvalósítása megtalálható a GitHub oldalon.