Az enyém pascalban még 5 perc alatt sem futott le :D Lehet ideje lenne elkezdenem tanulni a C-t... Azt mondták Pascalban iszonyatrossz az objektumorientáltság, ezért nem is fogtam hozzá :) Amúgy grat a gyors algoritmusodhoz ;)

Szerintem Pascalból C++-ra viszonylag egyszerűen, fájdalommentesen át lehet térni, mert a megszokott függvények egy kis utána olvasás után szinte ugyanúgy megvalósíthatóak. Viszont nekem úgy tűnik, hogy a C++ sokkal nagyobb szabadságot ad a megvalósításban. Ezeknek a lehetőségeknek a megismerése és használata számomra elég bonyolultnak tűnik, de kicsit barátkozva a lehetőségekkel a Pascal-t már nagyon korlátoltnak találtam és le is szoktam róla. A Java-ban viszont azt szeretem, hogy bár a C++-hoz képest nekem kötöttnek tűnik, alapból tele van egy halom hasznos, könnyen kezelhető library-val, így kevés tudással is egyszerű benne olyan függvényeket megvalósítani, amelyekről a Pascal-os korszakomban legfeljebb csak álmodhattam. Emellett a Java programozás rákényszeríti az embert egy, a Pascaltól gyökeresen eltérő szemléletre. A C++ ilyen szempontból számomra egy lépcső volt a Pascal és a Java között. Lehet vele ökörködni pascalos stílusban, és lehet vele tovább lépni a Pascalon. De a Java számomra sokkal egyszerűbb, mint a C++. Szerintem mindenképpen érdemes valamilyen irányban túllépni a Pascalon, és a Delphi rossz irány. Azt is próbáltam. Kecsegtető Pascal után, de a C++ vagy a Java-hoz képest elcseszett dolog.

Javítottam az algoritmuson. 10^8-ig az összes prím szám megszámolása 3 másodpercre csökkent.

10^9-ig az összes prím szám megszámolása 34 másodperc. Pillanatnyilag nincs ötletem, hogyan lehetne ezen még tovább gyorsítani, de gondolkodom rajta.

De akkor ez most azt jelenti, hogy a 10 számjegyű prímeket hamar meg tudod már találni ezzel az algoritmussal, nem?

az megkérdezhetem, hogyan keresed a prímeket?:) mert szerintem a gyökéig osztogatóssal ezt lehetetlen megoldani.még arra gondolok, hogy egy nagyon nagy tömbben mindig kivenni az i. és k*i. elemet, ( k eleme a pozitív egész számoknak ) majd növelni i értékét.

Igen, a 10 számjegyűeket elvileg megtalálom, de az még mindig sok idő. Egyelőre 10^9-ig mértem a sebességét, így csak az összes legfeljebb 9 jegyű prím számot találtam meg 34 másodperc alatt. Természetesen ebben nincs kiíratás, csak megszámoltattam.

Zseni vagy :)
Azt hiszem pár oldallal ezelőtt ajánlotta tulip a prímszitát, ami pont ezt csinálja.
Azóta belefutottam, hogy létezik egy komplementer prímszita eljárás is, esetleg azt kellene kipróbálni.

1, Legenerálom a prím számokat a vizsgálandó legnagyobb szám gyökéig.
2, Megadok egy 50.000 elemes boolean tömböt (50.000 fölött nem gyorsult tovább) és darabonként eratoszthenészi szitával fedem le a teljes tartományt. De mindig csak egyetlen tömb van jelen a memóriában, azaz tologatom a lefedő tömböt.

Tehát először megvan az 1-es pont, ezt egyszer végzem el. Ez után, ha valamelyik számról el akarom dönteni, hogy prím-e, pl. a 120121-ről, akkor a program megvizsgálja, hogy le van-e fedve eratoszthenészi szitával. Ha nincs, akkor 120121-től kezdődően 120121+49999-ig elkészíti az eratoszthenészi szitát, figyelembe véve, hogy a tömb 0-49999-ig van sorszámozva és a 0 itt a 120121-et fogja jelölni. Természetesen itt is csak a gyök(120121+49999)-ig folyik a vizsgálat.

Hogy érthetőbb legyen. Ha úgy választunk meg 2 vizsgálandó számot, hogy a különbség köztük nagyobb, mint az 50.000-es tömb, pl. 2 és 120121-ről szeretnénk eldönteni, hogy prímek-e, akkor megkeresi az algoritmus 2-50001-ig az összes prímet és megkeresi 120121-170120 között az összes prímet, tehát egy halom felesleges számolást végez. Ellenben ha pl. megnézzük a 2, 11201, 503, 57,45511, 27 számokra, akkor csak egyetlen, 2-49999-ig tömböt fog kiszámolni.

Tehát ez az algoritmus akkor igazán gyors, ha sorban növekvő elemeket akarunk vizsgálni.

Átgondoltam. 6-ból 4 oszlopot zár ki és a maradék esetek további vizsgálatot igényelnek. Viszont a 4 kizárt oszlop tartalmazza az összes páros és az összes 3-al osztható számot, amelyet egyébként is az elsők között zárunk ki a prímszám keresések alkalmával, így valójában nem gyorsít semmit, csak egy felesleges kört futunk előtte.