Prímkeresési algoritmusok
Tartalomjegyzék
Bevezetés
A prímszámok keresése alapvető feladat a programozás és az algoritmusok világában. A prímszámokat számos alkalmazásban használjuk, például titkosításban, játékelméletben és matematikai modellezésben. Az egyik leghatékonyabb algoritmus a prímszámok keresésére az Eratoszthenész Szitája nevezetű algoritmus, amelyet egy ókori görög matematikus, Eratoszthenész fejlesztett ki. Ebben a cikkben áttekintjük az algoritmus működését, az alapelveit és megvalósítását Java nyelven, de előtte átnézünk pár kevésbé hatékony implementációt is.
A prímkeresés fontossága
A prímszámok megtalálása a hagyományos módon, vagyis minden számot egyenként ellenőrizve, nagyon időigényes lehet, főleg nagy számok esetén. Ha például szeretnénk tudni, hogy az 1 és 1 millió közötti számok közül melyek a prímszámok, akkor a hagyományos módszerekkel óriási számítási teljesítményre lenne szükségünk. Itt jön képbe az Eratoszthenész Szitája algoritmus, amely sokkal hatékonyabbá teszi a folyamatot. A következő két fejezetben megnézzük a naiv implementációt és a szitás algoritmusunkat.
A naiv algoritmus
Ismételjük át először a prímszám definícióját: prímszámnak azt a pozitív egész számot nevezzük, amelynek pontosan két darab osztója van a természetes számok között: 1 és önmaga. Ebből kifolyólag az 1 tehát nem prím, hiszen annak egy darab ilyen osztója van.
Éppen ezért a naiv (kevésbé hatékony) implementáció a prímkeresésre egy adott tartományban az lenne, hogy a tartományban minden egyes adott számról megnézem, hogy 1 és önmaga között biztosan nincs-e osztója. Ha erről megbizonyosodtam, akkor kizártam minden osztót, ezért bebizonyítottam, hogy az adott számnak biztosan nincsen osztója. Ilyen algoritmusoknál az 1-et általában még manuálisan ki kell zárni, hiszen az sem számít prímnek. Nézzünk egy ilyen algoritmust:
import java.util.ArrayList;
import java.util.List;
public class NaiveImplementation {
public static void main(String[] args) {
System.out.println(getPrimesUntil(1_000_000)); // meghívom a függvényt azzal a bemeneti értékkel, ameddig a prímeket keresni szeretném
}
static List<Integer> getPrimesUntil(int n) {
List<Integer> primes = new ArrayList<>();
for (int i = 1; i <= n; i++) { //1 és n között keresem a prímeket
if (isPrime(i)) {
primes.add(i);
}
}
return primes;
}
private static boolean isPrime(int number) {
if (number == 1) { // ha a bemeneti paraméter 1, akkor a szám nem prím
return false;
}
for (int i = 2; i < number; i++) { // a szám minden egyes lehetséges osztóját végignézem 2-től number-1-ig, és ha találok ilyen osztót, akkor a szám nem prím
if (number % i == 0) {
return false;
}
}
return true; // ha végigmentem, és nem találtam osztót, akkor a szám prím
}
}Ennek az algoritmuselméleti komplexitása O(n2), hiszen végig kell mennem a teljes számtartományon, és azon belül még egyszer végigmegyek szinte az egész tartományon, hogy az összes osztót kizárjam.
Az optimalizált naiv implementáció
A következő lépés az, ha rájövünk arra, hogy egy számnak osztópárjai vannak, és nem kell 2-től a szám-1-ig elmennünk ahhoz, hogy biztosan kizárjuk azt, hogy vannak-e egyéb osztói a számnak 1-en és önmagán kívül.
Nézzük például a 12 osztóit:
- 1
- 2
- 3
- 4
- 6
- 12
Egy kis gondolkodás után azonban rájöhetünk, hogy ezek az osztók párokban vannak jelen:
- 1*12 = 12
- 2*6 = 12
- 3*4 = 12
- 4*3 = 12
- 6*2 = 12
- 12*1 = 12
Ebből kifolyólag viszont ebben az esetben például elég 3-ig elmennünk, és az összes osztópárt kizártuk, hiszen utána az osztópárok már ismétlődnek. Kérdés, hogy általános esetben meddig kell mindenképp elmennünk, hogy kizárjuk az összes lehetséges?
Ha egy kicsit gondolkozunk, rájövünk, hogy ez a szám négyzetgyöke lesz. Nézzük meg egy négyzetszám, a 36 osztópárjait:
- 1*36
- 2*18
- 3*12
- 4*9
- 6*6
- 9*4
- …
Ebből látszik, hogy a szám négyzetgyöke után már felesleges menni, hiszen a négyzetnél nagyobb osztókat már kiszűrtük. Így tehát rájöttünk, hogy az isPrime nevű metódusunkban nem kell a számig elmennünk, elég csak a négyzetgyökéig, így azt a metódusunkat a következőképpen módosíthatjuk:
private static boolean isPrime(int number) {
if (number == 1) {
return false;
}
for (int i = 2; i =< Math.sqrt(number); i++) { // ez az egyetlen sor módosul
if (number % i == 0) {
return false;
}
}
return true;
}Ezt az egysoros változtatás komoly nyereséget hoz nekünk teljesítmény tekintetében. O(n2)-ről O(n*sqrt(n))-re optimalizáltunk.
Számokkal kifejezve ez 10000-ig történő prímkeresés esetén annyit jelent, hogy az optimalizált algoritmusunk 100 000 000 művelettel korreláló helyett 1 000 000-val korrelálót végez el, ami még ennél a viszonylag kis n-nél is látszik, hogy komoly sebességnövekedést jelent.
De van még ennél is előnyösebb algoritmus!
Eratoszthenész szitájának algoritmusa
Eratoszthenész
Eratoszthenész egy ókori görög matematikus volt, aki időszámításunk előtt 276-ban született. Rengeteg dolog fűződik a nevéhez, például ő volt az első, aki becslést adott a Föld átmérőjének hosszára, de a Nap átmérőjének hosszára is végzett számításokat. Számunkra a legfontosabb kontribúciója viszont a szitáló algoritmusa, amelyet a következő alfejezetben részletezünk.
Az algoritmus
Az algoritmus röviden leírva annyi, hogy a 2-től felfele haladva kizárjuk minden prím szám többszörösét. Amelyik szám már ki van zárva, annak a többszörösei is ki vannak zárva, amelyik pedig nem került kizárásra, az értelemszerűen prímszám. Egyszerű, ugye? 🙂
Megvalósítás Java-ban
A megvalósítás egy nagyon egyszerű módja, ha létrehozunk egy akkora boolean tömböt, amennyi számról el akarjuk dönteni, hogy prím-e vagy nem. Az adott indexen mindig azt tároljuk, hogy az indexhez tartozó szám prím-e vagy nem.
Alapértelmezetten mindent prímnek tekintünk, és szépen, felfele haladva elkezdjük kizárni a többszörösöket:
public static List<Integer> getPrimesUntil(int number) {
boolean[] sieve = new boolean[number + 1];
Arrays.fill(sieve, true); // ez a lépés algoritmikai szempontból kihagyható, de átláthatóbb, ha azt, hogy prím egy adott érték igazzal jelöljük
for (int i = 2; i * i <= number; i++) { //elmegyek 2-től a szám négyzetgyökéig, és
if (sieve[i]) {
for (int j = i * i; j <= number; j += i) { // kizárom a szám többszöröseit
sieve[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= number; i++) {
if (sieve[i]) {
primes.add(i); //beteszem egy listába az output-ot
}
}
return primes;
}
A szita algoritmikai hatékonysága sokkal jobb a többi bemutatott prímkereső algoritmusénál: O(n*log(log(n)), ami 10 000-es inputnál körülbelül 6000 műveletet jelent az előző fejezetben lévő 1 millióval szemben.
Javaslom, hogy hasonlítsd össze a három implementációt, és kellően nagy inputoknál látni fogod, hogy mennyivel gyorsabb ez az algoritmus. Ugyanakkor fontos megemlíteni, hogy az Erastothenes szitája a cache miatt (a kódban ez a boolean tömb), tehát ennek a space complexity-je is O(n) de a gyakorlatban erre is vannak optimalizációs megoldások.
Videókurzusunk
Érdekel a téma? Java sorozatunkban is foglalkozunk prímekkel, ettől a résztől kezdődően:
Különösen ajánlom ezeknek a megnézését, mert itt olyan fontos témakörökről is szó van, mint a stream-ek vagy a szálkezelés. Természetesen mind algoritmuselméleti, mind a Java eszköztáraival kapcsolatos témákat mélységében tárgyaljuk egy éves junior képzésünkön: olyan tudást adunk át neked, amik lehetővé teszik az elhelyezkedésedet és a képzés után is folyamatosan segítünk a karrieredben.
Összefoglaló
A cikk végén egy összefoglaló táblázatban szemlétetem a tanultakat:
| Algoritmus | Leírás | Time complexity | Space complexity |
| Naiv implementáció | Elindul 2-től, és minden egyes számnak végigmegy a potenciális osztóin 2 és n között, hogy kizárja az adott számot | O(n2) | O(1) |
| Optimalizált naiv implementáció | Elindul 2-től, és minden egyes számnak végigmegy a potenciális osztóin 2 és n négyzetgyöke között, hogy kizárja az adott számot | O(n*sqrt(n)) | O(1) |
| Eratoszthenész szitája | Hatékony módszer nagy számok esetén is; 2-től indulva kiszűri minden szám többszörösét, és csak a prímek maradnak bent. | O(n* log(log(n)) | O(n) |
Köszönöm a figyelmet, tarts velünk legközelebb is!
Szerző: Nagy Csongor
