Ez pedig egy ismert szamspiral prim szamok abrazolasahoz. Van regeteg ilyen geometriai alakzatokra valo primabrazolas, nem csak az Arkhimedesz spiralra. Ezekkel a modszerekkel lehet kovetkeztetni, hogy hol helyezkednek el primek nagy valoszinuseggel.
html kodokat frankon ignoralja a cms
<i>"Én egyszer olyat próbáltam csinálni, ami egy dinamikus tömbben eltárolja a talált prímeket, és úgy mûködött, hogy "kilyuggatta" a számegyenest."</i>
<i>"És az is biztos, hogy egy 1024 bites prímtesztben nem lehet tárolgatni már a prímeket."</i>
De lehet, a megfelelo eszkozok birtokaban es/vagy tartomanyokra kell bontani, csak a referenciaertekeket kell tarolni es minden tartomany megkezdese elott a regit elmenteni, az ujat pedig betolteni a referenciaertekekkel egyutt.
Ezert van az, hogy titkositashoz nem ilyen modszereket alkalmaznak, hanem relativ primeket keresnek. Pl, Ferman teszt. Meg van meg tengernyi modszer primszamok keresesere.
Szép és jó, de ha titkosítani akar a szerencsétlen, akkor 128-4096 bites prímszámokra lenne szüksége. Ezeket hogyan találja ki ilyen Móriczka-programmal? :) Én egyszer olyat próbáltam csinálni, ami egy dinamikus tömbben eltárolja a talált prímeket, és úgy mûködött, hogy "kilyuggatta" a számegyenest. Tehát ha megvolt egy prím, akkor a tömb prímhez tartozó elemébe (nx2-es tömb) eltárolta a prím kétszeresét. Ha ez foglalt volt, tehát már egy másik prím volt benne, akkor hozzáadta megint a prímet, egészen addig, míg egy új "lyuk" nem keletkezett. Nagyon nem optimalizáltam ki, meg lehet, hogy láncolt listával volt ez a második fele, nem pedig nx2-es tömbbel, de döglassú volt :) És az is biztos, hogy egy 1024 bites prímtesztben nem lehet tárolgatni már a prímeket. Rengeteg van. Viszont ha valaki akarja, próbálja meg az N-edik prímig venni a prímek összegét. Egy meglepõen szabályosnak tûnõ függvényt kapunk, de valahogyan mégsem lehet rá illeszteni függvényt pontosan. Valószínûleg tényleg csak látszólag szabályos.
Alakul.
Termeszetesen a gyokvonasos megoldasnal van jobb is viszont a Te progidban mar ez is nagy elorelepes.
Erdemes meg figyelni arra, hogy ne vegezd el a gyokvonast a belso ciklus minden ismetlodesenel. Vegyel fel egy segedvaltozot amibe kiszamolod eloszor a gyokot, majd a for ciklus befejezo feltetelenel ezt adod meg. Ugyanis, akarhanyszor lefut a belso ciklus, minden alkalommal gyokot von, de a te esetedben csak a kulso ciklus aktualis ertekenek gyoke szamit.
Ez nagyon sokat fog dobni a teljesitmenyen es te is sokat fogsz tanulni belole. Ha ezzel meg vagy, akkor probalkozhatsz az 5-tel oszthatok kiejtetesevel is, mert ottel nem vegzodik primszam, kivetel az 5.
Termeszetesen ezt a programocskat szinte a vegtelensegig lehet meg optimalizalni, de ebbol fogsz tanulni.
Megcsináltam, hogy csak a páratlan számokat nézze, hogy csak a négyzetgyökükig ellenõrizzen, és csak azokat írja ki, amik prímek, és most csak 7 perc volt, míg végigment, és a kapott fájl egyezik az 1 óra alatt végbement elõzõ keresés által eredményezett fájlal, szóval jól mûködik az optimalizálás után is a programom.
"Miert iratod ki az "i" erteket? Felesleges. Eleve annyi szam lesz a "fajlban" mint amennyi primet talaltal es a sorvegek megszamolasaval mindig a szukseges szamra tudsz allni, ha kesobb fel is szeretned hasznalni a generalt szamokat." Mert szeretném látni hol tart a folyamat, de mondtam, hogy ezt tudom, hogy sokat lassít, majd kiveszem.
"3. Miert messz el (i-1)-ig a ciklussal? 6x3 is 18, meg 3x6 is. Elegendo a gyokeig elmenned." Ez a példa kicsit megkevert, de ugye arra gondolsz, hogyha pl a 25-öt vizsgálom, akkor elég 5-ig megnéznem a maradékos osztást?
4. Miert vegzel el ketmillio maradekos osztast? Azt ugy is tudjuk, hogy 2 kivetelevel minden masodik szam prim, tok felesleges oket ellenorizni. Leptessed kettesevel a ciklust es ugrald at a paros szamokat. Ez igaz, kicsit siettem, ezért ezt véletlenül kihagytam.
"5. Siman irassad ki a terminal ablakba egymas ala a szamokat, majd iranyitsd at fajlba." Dark Basic Pro meg a terminalablak... A Dark Basic Pro egy 3D játékok készítéséhez kifejlesztett ide+compiler. Még a sima szövegkiírást is DirectDraw-al oldja meg. Bár mondjuk van egy FreeBasic nevû compiler, ami terminálablakba nyomja ki a dolgokat, talán átírom kicsit a progit, és megpróbálom azzal, és akkor tudom használni a fájlba átirányítást.
"4. Miert vegzel el ketmillio maradekos osztast? Azt ugy is tudjuk, hogy 2 kivetelevel minden masodik szam NEM prim, tok felesleges oket ellenorizni. Leptessed kettesevel a ciklust es ugrald at a paros szamokat."
Gyokvonas sem kell igazan, az is kikoszobolheto, eltarolva egy szamot es negyzetet, a szamig ellenorzod, a negyzetenel kisebb gyanisitottakra, amint nagyobb szamokat kell vizsgalni a szamot noveled egyel, es ujra szamolod a negyzetet. Ez egy hasonlitast eremenyez, nemely elysetben egy inc + szorzast is, ami meg mindig kevesebb mint egy gyokvonas ido igenye.
Valamint eleg csak a mar megtalt primmekkel probalkozni mod ra.
Ha csak 1000000 kellenek akkor szita modszert is lehet hasznalni. Nagyabol: 0. 10000000 elemu bitvektor kezdo ertek true. , p=2 1. minden pedik megjelol falsnak 2. a legkisebb meg nem hasznalt true val jelzett index el legyen egyenlo p 3. ha p meg nem eleg nagy (<1000), ugras 1 -re.
Ami true maradt az prim. Lehet kifirkalni.
Valami ilyesmi formaban fogod megkapni, ha atiranyitod a konzol kimenetet a fajlba.
Meg egy hasznos tipp: az igy kapott fajlt beimportalhatod excelbe es jatszadozhatsz a primekkel grafikonon.
Elirtam a szamozast. Szorri.
1. Ez a faktorizacio. 3. Nem a nyelv miatt ilyen atkozottul lassu, hanem azert mert egy csomo olyan muveletete elvegzel ami felesleges.
2. Miert iratod ki az "i" erteket? Felesleges. Eleve annyi szam lesz a "fajlban" mint amennyi primet talaltal es a sorvegek megszamolasaval mindig a szukseges szamra tudsz allni, ha kesobb fel is szeretned hasznalni a generalt szamokat.
3. Miert messz el (i-1)-ig a ciklussal? 6x3 is 18, meg 3x6 is. Elegendo a gyokeig elmenned.
4. Miert vegzel el ketmillio maradekos osztast? Azt ugy is tudjuk, hogy 2 kivetelevel minden masodik szam prim, tok felesleges oket ellenorizni. Leptessed kettesevel a ciklust es ugrald at a paros szamokat.
5. Siman irassad ki a terminal ablakba egymas ala a szamokat, majd iranyitsd at fajlba.
pl mukodjon kb. igy:
primgen.exe 3 5 7 11 ...
ha igy mukodik, akkor intitsad el igy: primgen.exe > primszamok.txt
Ha lefutott, akkor visszakapod a konzolt es meg lesz irva a fajl is.
"A kozismert faktorizacios generalasi metodust hasznalja." Ezt én nem ismerem, ezért saját módszert használok: for i=1 to 1000000 print i for i2=2 to i-1 if i MOD i2=0 then p=0 : exit if i MOD i2<>0 then p=1 next i2 if p=1 then pr(ptr)=i : ptr=ptr+1 next i
Dark Basic Proban írtam a programot, C/C++-ban biztos sokkal gyorsabb lett volna, de még nem tanultam meg abban a fájlkezelést, a talált prímszámokat meg ilyen nagy mennyiségnél mindenképp ki kell írni fájlba, ha meg akarom õket nézni.
Lehet, hogyha a print i-t kihagytam volna, akkor sokkal gyorsabb lett volna, de szerettem volna látni, hogy hol tart.
Az itt benchmarkkent hasznalt primszamgeneratort csak osszecsaptam, semmi optimalizalas, semmi extra. A kozismert faktorizacios generalasi metodust hasznalja. Az Eratosthenes metodussal tizedmasodpercek alatt szokott vegezni ugyanez a gep, ugyanezzel a vizsgalati tartomannyal.
Én írtam egy programot az elõbb, ami 1 és 1000000 között megkeresi az összes prímszámot, kb 1 órába telt amíg végzett, összesen 78497 prímszámot talált, a legnagyobb a 999983.
Azta 700 gépet értelmes projectre is használhatták volna. Ez az egész csak figyelemfelkeltésre jó.
Informatika és tudomány
