Prímkeresési algoritmusok

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(n²), 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 az anná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(n²)-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