menu
shopping_cart
0
KOSÁR

23. lecke

Prímszámkereső írás

lightbulb_outlineMegírjuk a prímszámkeresőt

Az előző fejezetben 3 érdekes rávezető példát láthatunk. Mindhárom megismert ötletet felhasználjuk a prímszámkereső összerakásához. Várjunk csak: Mi az a prímszám?

 Prímnek nevezzük azokat a természetes számokat, amelyeknek pontosan két osztójuk van a természetes számok között (maga a szám és az 1).

Például ők prímszámok:

2,3,5,7,11,13,17...

Ha az előző, az osztók darabszámát vizsgáló programban ellenőrzöd őket, akkor mindegyik esetén 2-őt fogsz a képernyőn látni, mivel csak 2 osztójuk van.

Kitérő

A prímszámokat az informatikában a titkosításhoz és az ál-véletlenszám generáláshoz használják.

  • A véletlenszám generálás egy nagyon fontos dolog az informatikában, mivel sok helyen előkerül: Gondoljunk csak a számítógépes játékokra, ahol az ellenfél véletlenszerűen viselkedik. Véletlenszámot generálni általában a számítógép belső órájának állapota alapján szoktak, mivel teljesen véletlenszerű, hogy az épp milyen értéket mutat. A másik módszer valamilyen külső véletlen forrás felhasználása. Ilyen például a kozmikus háttérsugárzás. Amikor tényleg teljesen véletlen, úgynevezett true random számokat szeretnénk kapni,(péládul tudományos kísérleteknél szükség van ilyenre) akkor egy speciális eszközzel felfogják az űrből érkező részecskéket, és ezek becsapódásai között eltelt idők adják a véletlenszámokat.

    • A prímszámokat is lehet véletenszámként kezelni, mivel véletlenszerűen következnek egymás után - de mégse, mert ha akarjuk, akár ki tudjuk számítani következő prímszámot, például egy olyan C programmal, amit mindjárt írunk. Ezért ők nem igazi véletlenszámok, hanem csak pszeudo-véletlenek, más néven ál-véletlenszámok.

A másik terület ahol a prímszámokat használják az a titkosítás.

  • Bizonyára neked is rémlik matekóráról a prímtényezős felbontás fogalma, amikor egy számot prímszámok szorzatára bontunk. Ha egy szám két nagyon nagy prímszám szorzata, akkor a prímtényezős felbontás kiszámítása nagyon sok időt és számítási kapacitást igényel. Az RSA titkosító algoritmus, ami az internetes kommunikáció során gyakran használt eljárás, erre alapul. Részletes leírása itt található. A lényeg annyi, hogy nagyon nagy prímszámokra van szükség a titkosítás elvégzéséhez, ezért az informatikában a prímszámok fontosak. A prímszámokra alapuló titkosítás nem feltörhetetlen, viszont nem érdemes a feltöréssel próbálkozni, mert több millió évet venne igénybe a mai modern számítógépekkel.

    • A prímszámok véletlenszerű egymásutánisága megdőlni látszik az ún. ABC-sejtés bizonyításával, ami a prímek közötti kapcsolatot írja le. Ez a prímszámokra alapozott titkosító algoritmusokra végzetes lehet. Egyelőre azonban nem sikerült bizonyítani: Index.hu cikk

A prímszámok keresése egy nagyon jó móka. Szerveződött is egy internetes közösség, akinek célja nagyobb és nagyobb prímszámok keresése. A közösség a tagjainak számítógépes erőforrását használja a prímszámkereséshez. 1 gép lassú. Kettő is – de több ezer gép már gyorsabban végzi a számítást. A Nagy Internetes Prímszámeresés közösséghez itt lehet csatlakozni: www.mersenne.org/freesoft ahol letölthetsz egy kis szoftvert, amit a gépedre telepítve az adatokat fogad a központtól és a processzorod szabadidejében beszáll a számításokba.

Lássunk neki

Lássunk neki a prímszámkereső program írásához. A feladat: Írjunk egy programot, ami elkezni kilistázni a prímszámokat megállás nélkül.

A program írásakor kihasználjuk a számítógép számítási teljesítményét, és első körben minden matematikai optimalizálást félretéve ”brute-force” módszerel minden osztást elvégeztetünk a géppel. Tehát:

Vesszük az 2-őt, és elosztjuk az összes nála kisebb 
pozitív egésszel és számoljuk az osztók darabszámát. 
Ha pont 2 lett a végén, ez prím 
és kiírjuk a képernyőre.

Vesszük az 3-at, és elosztjuk az összes nála kisebb 
pozitív egésszel és számoljuk az osztók darabszámát. 
Ha pont 2 lett a végén, ez prím 
és kiírjuk a képernyőre.

Vesszük az 4-et, és elosztjuk az összes nála kisebb 
pozitív egésszel és számoljuk az osztók darabszámát. 
Ha pont 2 lett a végén, ez prím 
és kiírjuk a képernyőre.

... és így tovább a végtelenségig

Mivel itt is az osztók darabszámát vizsgáljuk, ezért az előzőleg megírt osztók darabszámát kiszámító program lesz a mostani prímszámkeresőnk ”magja”. Ide is másolom még egyszer:

#include<stdio.h>

int main(){

    int szam;       //a vizsgált szám
    int i;      //ciklusváltozó
    int darab=0;    //osztók száma

    printf("Adj meg egy számot és én ");
    printf("megmondom hány osztója van!\n");

    scanf("%d", &szam);

    for(i=1; i<=szam; i++)
    {
        if(szam % i == 0)
        {
            darab++;
        }
    }

    printf("%d darab osztója van", darab);

return 0;
}

osztokszama.c c 12

Írtsuk ki a felesleges részeket belőle:

  • nem kell beolvasás, mert a felhasználóval nem kommunikálunk, magától fog működni a program
  • nem kell kiírni a végén a darabszámot sem
#include<stdio.h>

int main(){

    int szam;
    int i;
    int darab=0;

    for(i=1; i<=szam; i++)
    {
        if(szam % i == 0){ darab++; }
    }

return 0;
}

osztokszama_min.c c

Itt van a mag. A mi feladatunk az, hogy a ”szam” nevű változót növeljük, azaz szépen sorban kezdjük el vizsgálni a pozitív egész számokat, hogy hány osztójuk van.

A mag köré ezért jön egy FOR ciklus ami ezt a szám változót lépteti.

  • Ez a külső FOR ciklus 2-ről induljon,hisz ez az első prímszám
  • egyesével növekedjen, mert minden számot meg akarunk vizsgálni, hogy prím-e
  • és soha ne álljon le, azaz nem kell feltétel rész neki
#include<stdio.h>

int main(){

    int szam;
    int i;
    int darab=0;

    for(szam=2;     ; szam++)
    {
        for(i=1; i<=szam; i++)
        {
            if(szam % i == 0){ darab++; }
        }
    }

return 0;
}

primszamkereso_felkesz.c c

Már 80%-ban készen van a programunk. Már csak ki kéne írni azokat a számokat, amiknek pontosan 2 darab osztója van. Egyszerűen a ”mag” után leírunk egy IF-et, ami ezt megvizsgálja.

A ”mag” előtt pedig nullázni kell a darabszámot, hisz minden egyes új szám vizságlatakor újból (előről, 0-ról) kezdjük a darab számolását.

#include<stdio.h>

int main(){

    int szam;
    int i;
    int darab=0;

    for(szam=2;     ; szam++)
    {
        darab = 0;

            for(i=1; i<=szam; i++)
            {
                if(szam % i == 0){ darab++; }
            }

        if( darab == 2){ printf("%d\n", szam); }
    }

return 0;
}

primszamkereso_kesz.c c

Készen van a prímszámkereső! Foglaljuk össze a tudnivalókat:

  • A külső FOR ciklus mindig kijelöl egy újabb és újabb számot. 1,2,3,4,5,6 ...
  • A MAG ami egyébként a külső ciklusig fut, meghatározza osztóinak darabszámát.
  • A KIÍRÁS kiírja a számot, ha az osztók darabszáma pont 2.

A program megállás nélkül listázza a prímszámokat, ha offline teszteljük a kódot. Persze szépen le is lassul, mert egyre távolabb következnek egymás után a számok.

Vegyük észre, hogy az előző fejezetben bemutatott kis programok mindegyik elemét tartalmazza a prímszámkeresőnk:

  • a belső FOR ciklus a külső aktuális értékéig fut (a háromszög rajzolós példa alapján)
  • az osztók darabszámát maradékos osztással határozza meg

Na ezt nevezem én művészetnek!