Melyik a leghatékonyabb algolitmus primszámkereséshez?

Nagyságrendileg mennyire kell gondolni? 1-től valameddig keresés? Vagy tesztelés?

Memória korlátlan?

[link]

Itt sok érdekeset írnak, kódok is szerepelnek. Talán párhuzamosan érdemes fájlba is írnod, mert napokig fog futni az algoritmus.

Kicsit magasra tetted a lécet, lehet nem lesz elég a memória.

[link]

Ha a pi(n)-t beszorzod a 8 byte-al, kijön a szükséges tárhely.

Wampa!

Elkényelmesedtek ezek a mai programozók... pedig volt olyan idő, amikor még akadt olyan, hogy EGY EGÉSZ FILE-t :-D nem tudott egyben beolvasni a memória :-) mégis megoldották :-P

Hisz vannak nagy háttértárak is.

Lehet hogy elkényelmesedtem és valamit elszámoltam, ezt vállalom.

[link]

Viszont ez az érték nekem a háttértáramhoz is nagynak tűnik.

-> a párosokat külön ellenőrizd

Valahogy így:

if(szam % 2 == 0)

if(szam == 2)

Kiir("Prím");

else Kiir("Nem Prím");

....

-> csak a szám gyökéig keresed az osztóit

-> a szám gyökét először letárolod egy változóban

-> az osztót 2-vel növeled

Valahogy így:

int gyok = sqrt(szam);

int oszto = 3;

while(oszto <= gyok && szam % oszto != 0)

oszto += 2;

...

Ellenőrzés:

if(szam % oszto == 0)

Kiir(Nem prím);

else

Kiir("Prím");

....