Prímszámok C-ben?

Eratoszthenész szitája erre egy jó megoldás (de a végtelenig nem fogod tudni kiíratni a prímszámokat, mivel a számoknak nincs végük - ki hitte volna?)

[link]

Még programkód is van :)

Persze ha nyitott végű a keresés (nem tudod előre, meddig keresel), nem praktikus így implementálni, egyszerűbb csak letárolni az eddig megtalált prímeket és azzal ellenőrizni.

A végtelenig sokára fogsz eljutni. Ez olyan feladat, amire a megoldó programokat a tudósok gépi kód szinten optimalizálják és picit nagyobb kaliberű gépeken futtatják.

Amúgy meg:

Megy a ciklusod 2-től végtelenig (?), és a ciklusváltozót megvizsgálod, hogy prím-e. Ha igen, kiírod, ha nem, akkor nem. Azt, hogy 100 ezernél fájlt váltson pedig pl. úgy oldhatod meg, hogy számolod a kiírt számokat, ha eléri a 100 ezret, akkor áttérsz egy másik fájlra és nullázod a számlálót. Például.

Azt, hogy ezt C-ben hogy oldod meg: Google segít a szintaxisban és a fájlkezelő függvényekben.

Legyen egy jó tesztelő függvényed, ami megmondja, hogy a szám valószínűleg prím. Nem biztos, hogy az, de sokkal gyorsabb, mint a szita. A Miller-Rabin teszt már előre meg van írva.

Ehhez kell egy függvény, amely adott számszor meghívja a tesztet, és eldönti, hogy valószínűleg prím.

Ezt hívogathatod a ciklusban, de a fájlokat addig generálhatod, amíg a long long korlátját át nem lépi, vagy amíg meg nem telik a lemez. Nem tudom, melyik következne be előbb.

A kellemetlenség az, hogy amíg fut, addig nem zárhatod le a gépet.

@14:10

Nem vagy tisztában a dolgokkal.

"Nem biztos, hogy az, de sokkal gyorsabb, mint a szita."

Ezt empirikusan is megállapítottam hogy nem igaz : http://www.gyakorikerdesek.hu/szamitastechnika__programozas_..

Lemértem a futási időket.

Akkor valóban gyorsabb a Miller-Rabin teszt ha 1 konkrét szám érdekel hogy prím e és ez a szám elég nagy. A szita az előállítaná a nála kisebb prímeket is ez esetben feleslegesen.

Viszont ha az összes prímet elő akarom állítani 2-től N-ig akkor a szita gyorsabb, sőt nem is ismerek nála gyorsabbat.

"a fájlokat addig generálhatod, amíg a long long korlátját át nem lépi, vagy amíg meg nem telik a lemez. Nem tudom, melyik következne be előbb."

A prímszámok eloszlása 1-től N-ig pí(N), ha N tart végtelenbe akkor pí(N)/(N/log_e(N) tart 1-hez.

long long helyett inkább unsigned long long-ot használnék.

64 bites szám aminek 2^64-1 a felső határa. 1-től 2^64-1-ig (2^64-1)/log_e(2^64-1) darab prím van jó közelítéssel, 1% alatt van a hibahatára a közelítő függvénynek, ekkor az alsó becslésem az hogy 1512775 Terabyte-ra lenne szükség ennyi prímet eltárolni. Felső becslés 7942070 Terabyte. Az alsó becslésnél sokkal több lehet a valóságban, a felsőnél sokkal kevesebb. Számolhattam volna pontosabb alsó és felső becslést, de nem akartam vele vacakolni. A lényeg hogy egyértelmű hogy lenne e ennyi háttértára.

"Legyen egy jó tesztelő függvényed, ami megmondja, hogy a szám valószínűleg prím. Nem biztos, hogy az, de sokkal gyorsabb, mint a szita."

"A kellemetlenség az, hogy amíg fut, addig nem zárhatod le a gépet."

Ez ellentmondás. A szita jóval gyorsabb és hatékonyabb módszer. Ami egy program szempontjából nagyon durván fontos tulajdonság.

"hogy a szám valószínűleg prím. Nem biztos, hogy az"

Ilyen hozzáállással ne menj el programozónak. Ez így egy baromi nagy hanyagság és hibalehetőség.

""hogy a szám valószínűleg prím. Nem biztos, hogy az"

Ilyen hozzáállással ne menj el programozónak. Ez így egy baromi nagy hanyagság és hibalehetőség."

Ezt szándékosan nem mondtam hiszen ez nem igaz, ebből az egy mondatból látszik hogy nagyon sok mindent nem tudsz a témával kapcsolatban. Gyakorlatba nagyon jól használható és használják is pl az RSA titkosító algoritmusban. Hiszen nagyon hatékonyan lehet nagy számokat prím tesztelni (2^512 és 2^1024 köztieket keresnek általában az RSA-val). Egyszerű osztogatással a naprendszer élettartama nem lenne elég, akkor sem ha csak a négyzetgyökéig megyünk.

Féloldali hibás Monte Carlo algoritmus a Miller-Rabin teszt vagyis ha a teszt azt mondja hogy nem prím az biztos, ha azt hogy prím legalább 50% valószínűsége hogy prím. Ha random alapokkal S-szer megismételjük a tesztet akkor 1:2^S a tévedés valószínűsége, ha 100x megismételjük akkor olyan kicsi az esélye hogy elfogadható. Évszázadokig ha használnám akkor is sokkal kisebb lenne annak a valószínűsége hogy minimum 1x "tévedett" az algoritmus mint az hogy összesen 1x veszek egy lottószelvényt és teli találatom lesz. A gyakorlatba szokták ötvözni a Fermat prím tesztel így gyorsabban kiszórja a nem prímeket.

"1:2^S a tévedés valószínűsége"

Vagy még kisebb.