Programozás

[Redback]

Originally Posted by tulip

Átírtam C-re a Te algoritmusodat lényegi változtatás nélkül és 4 perc 8 másodperc alatt futott le. (Ez 64 bites linux alatt futott, a NetBeans mérte az időt E5200-as procival.) C++-ról viszont az enyémet nem tudom átírni pascalra, mert objektum-orientáltan írtam és nem tudok annyira pascal-ul.
Így néz ki a Tied, hogy lásd, nem változtattam semmit:


#include <stdlib.h>
#include <math.h>
#include <stdio.h>

bool prim(long unsigned long szam) {
long unsigned long gyok, i;
gyok = round(sqrt(szam));
i=3;
while (i<=gyok) {
if (szam % i == 0) return false;
i++;
i++;
}
return true;
}



int main(int argc, char** argv) {
unsigned long k = 1;
for (long unsigned long i = 2; i < 50000000 ; i++) {
if (prim(i*2-1)) {
k++;
}
}
printf("%d", k);
printf("\n");
return (EXIT_SUCCESS);
}

Az enyém pascalban még 5 perc alatt sem futott le 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

[tulip]

Originally Posted by Redback

Az enyém pascalban még 5 perc alatt sem futott le 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.

[tulip]

Originally Posted by tulip

Futási idő 1 perc és 19 másodperc:
10^8-ig pontosan 5.761.455 db prím szám van.

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.

[Valezius]

Originally Posted by tulip

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?

[Andrew]

Szerintem még mindig ez ez a legjobb prímszám kereső program

[Redback]

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.

[tulip]

Originally Posted by Valezius

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

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.

[Valezius]

Originally Posted by Redback

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.

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.

[tulip]

Originally Posted by Redback

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.

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.

[tulip]

Originally Posted by Valezius

Zseni vagy
Azóta belefutottam, hogy létezik egy komplementer prímszita eljárás is, esetleg azt kellene kipróbá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.