Primkeresés - Hatékony megoldást tud' valaki?
Van egy olyan feladatom, hogy nagyon hatékonyan írassam ki a prímszámokat millióig...
Prímkeresésre van egy szokott megoldásom ami annyiból áll, hogy végignézegetem az osztókat a szám gyökéig és ha egyik sem osztotta akkor a szám prím, így egy sima "eldöntés tétele" az egész (amit ugye beleágyazok egy sima számlálós ciklusba azt ha valamelyik prím volt akkor kiíratom.)
Nos ennél hatékonyabb megoldásra lenne szükség, úgyhogy elkezdtem felírogatni a számokat 0-9 10-19 20-29.. szépen egymás alá és azt vettem észre, hogy néhány sor kiesik, ill. néhány sor majdnem teljesen kiesik, ha az első sort leszámítjuk. A prímes sorokban nem tudom, hogy van e valami rendszer ami alapján követik egymást a prímek, mert ez alapján talán ki lehetne építeni egy hatékonyabb módszert a keresgélésre.
A válaszokért előre is köszi és ha lehet akkor a c++ nyelvet/ a mondatszerű leírást (esetleg Java-t) preferálnám, mert legjobban azokhoz értek és tudok hozzászólni ilyen téren.
Más megoldást is szívesen elfogadok, nem muszáj az enyémet folytatni, csak ha olyasmit írtok, felőlem lehet bármennyire bonyolult csak azért vezessétek le, hogy mi miből következik, hogy én is értsem köszönöm(:
válasza:Hát igen, például a páros számok a 2-es kivételével mind kiesnek. Ez élből 5 oszlop a 10-ből. :)
Ezzel pölö lehet gyorsítani a te algoritmusodat, hogy 3-tól kezdve már kettesével lépkedsz.
A(z egyik?) hatékony módszer pedig Erasztothenész szitája:
Itt is vannak még gondolatok:
http://www.gyakorikerdesek.hu/szamitastechnika__programozas_..
válasza:Ha adott limitig az összes prímszám kell, akkor a szitánál hatékonyabbat nem fogsz találni. Az implementációt lehet tinkerelni. Például használj vectort, mert az fossá van optimalizálva.
Ezt billentyűzd be:
"Minden 3-nál nagyobb számot - szigorúan növekvő sorrendben - megpróbálunk elosztani az összes eddig ismert prímszámmal. Ha valamelyikkel az osztás sikerült, a szám nem prím (például a 4 osztható 2-vel). Ha egyikkel sem tudjuk osztani, akkor az adott szám is prím (például az 5). Ezt a számot hozzávesszük az eddig ismert prímek listájához."
válasza:iostream módszeréhez kiegészítés:
Minden 3-nál nagyobb _páratlan_ számot - szigorúan növekvő sorrendben - megpróbálunk elosztani az összes eddig ismert prímszámmal _a szám gyökéig_.
Wikipédián írnak szép prímteszteket, de milliós-milliárdos gyűjtésre szerintem így a leghatékonyabb. Ilyen soros-oszlopos válogatásra még nem láttam példát, elég random helyezkednek el a prímek.
válasza: válasza:Szvsz ha van egy fix felső határ, ami nem is annyira nagy, akkor a hardcodeoltnűl gyorsabb megoldás nem lesz.
A neten vannak hosszú prím listák, azt szépen kicsit faragod, berakod egy vektorba és kész.
Nagy lesz a fájl, de gyors. :P
(Algoritmusokból jobbnál jobbakat lehet találni a neten, ha az kell.)
Mmm.. Köszönöm a válaszokat végig olvastam mind és szerintem mindenki megérdemli tőlem a 100%ot(:
Fogtam beleírtam és felírtam egy Erathosztenész szitát, de tömböt használtam, vector helyett. Az baj?x.x mármint ha ront a sebességén az miért is van?
válasza:1. Alapvetően nem baj, csak korlátozza a mennyiséget. De ha előre tudod, mennyi elemed lesz, akkor teljesen jó.
2. Ronthat, számomra ismeretlen okokból. Valószínűleg a vectorban olyan optimalizálások vannak, amik egyszerű halandó számár nem érhetőek el.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!