48
prímek
-
Bnum #48 A wikipedia-ban is ír egy pár prímtesztről:
"http://hu.wikipedia.org/wiki/Pr%C3%ADmteszt"
A legjobb jelenleg az AKS-algoritmus, de ezekről nem sokat tudok.
Nagyon hatékonyan keresik a prímeket, illetve faktorizálják a számokat, de ezzel nem sokat lehet megtudni a prímek elhelyezkedéséről.
Nagy számoknál nem is ez a cél, de nincs is más alternatíva.
Több száz számjegynél lassan kevés lesz az univerzum eddigi ideje is a számítás elvégzéséhez.
Végül is az kevesebb mint 5*10^17sec.
Ha másodpercenként 10milliárdos lépésekben haladsz, az még mindig csak 5*10^27.
Mivel elég a négyzetgyökig számolni, akkor 2,5*10^55-ig kilehet számolni az összes prímet (ilyen feltételekkel).
S ettől még messze van a 600. :O)
-
pet0330 #47 Ennyi??? xD
Nincs rá valami jobb módszer mondjuk, hogy néhány számra meg se kelljen vizsgálni? -
#46
Fapados módszer, hogy 2től kezdve a szám négyzetgyökéig el kell osztogatni sorban a prímszámokkal az adott számot, és ha nincs olyan prímszám, amivel osztható, akkor a szám is prímszám. -
pet0330 #45 Azt tudom hogy a prímek osztói csak 1 és önmaguk.
Úgy gondoltam hogy ha hasraütök és mondok egy 600 jegyű számot akkor annak hogy keresik a prímosztóit. -
Bnum #44 Igazad van, pet0330 kérdését félre értettem.
A prímeket keresik (pl. Erasztotenész szitájával).
A prímek osztóit nem.
Mivel a prímek osztói: 1, és önmaguk. -
#43
Uhh..hát van ennél sokkal, de sokkal egyszerűbb algoritmus is... -
Bnum #42 A legprimitívebb:
Erasztotenész szitája.
n-ig kihúzod a 2 többszöröseit,
aztán a 3 többszöröseit,
aztán 5 többszöröseit,
aztán p többszöröseit,
Ezt folytatod n^1/2-ig.
Amit nem húztál ki, az prím. -
pet0330 #41 Amugy hogy is működik ez az algoritmus amivel keresik az osztóit? -
pet0330 #40 Sziasztok!
Áll.: Végtelen sok prímszám van.
Biz.: Szerintem INDIREKTEN a legegyszerűbb bizonyítani. Tegyük fel, hogy véges sok prímszám van. Ezután szorozzuk össze ezeket a számokot és adjunk hozzá 1-et. Ekkor egy olyan számot kapunk ami az eddigi prímszámokkal osztva 1 maradékot ad, tehát ez vagy egy prímszám vagy olyan prímosztói vannak amik nem voltak az eredetileg feltett prímszámok között. És ezt mindig el lehet játszani.......... -
Bnum #39 Itt a prímek már nem érdekelnek senkit? -
palack #38 Fölösleg4es ezzel a prímes titkosítással szenvedni, úgysem ott lopják el a kulcsot ahol gondolod! -
feketeribizli #37 A primszámaid fej vagy irással keverve, spórolásra késztethetnek. -
#36
Mivel a nyilvános kulcsú/asszimetrikus titkosítások (ilyen például az RSA) primszámokon alapulnak, ezért igen nagy a jelentőségük a primszámoknak.
Bővebben erről itt, itt. és itt olvashatsz.
Vagy ajánlom figyelmedbe Simon Singh Kódkönyv című művét. -
#35
gyakorlatban mire jók ezek a számok? gondolom nem hobbiból áldoznak ennyit a keresésükre..ha igen akkor elég elvetemült hobbi :D -
Zsoldos #34 Vizsgaztam 1x a profnal -
blackgamer #33 Prímkereső projekt -
Zsoldos #32 Gyurunek gyuru az. Csak egyebek hianyoznak neki.
({ .. -1 , 0, 1, 4, 6, 8 ...} , +, *) nem lehet gyuru, mert az osszeadas muvelet peldaul kivezet belole. (1+4=5 nem eleme a halmaznak)
Reg tanultam mar ilyesmit, arra emlekszem, hogy talalkoztam olyan strukturaval, amiben volt felbonthatatlan elem, de nem volt prim.. Talan vmilyen (nem test) feletti polinom polinom. Z[x]-en filoztam most, de ott is egybeesnek, igy a Q[x] is ugrott.. Majd irok ha eszembejut. Test feletti polinomgyuruben biztos megegyeznek. Talan konnyebben talalnank, ha nem a halmazt varialnank, hanem a "*", "+" muveleteket definialnank kicsit maskeppen. -
7evenb #31 akartam is írni, hogy ez nem gyűrű, de ezek szerint több gond is van vele:)
viszont akkor milyen példát lehet mondani, ahol a prím és felbonthatatlan nem egyezik?
R test feletti polinóm gyűrű? - az irreducibilis polinomok prímek is? (szerintem igen)
vagy:
({...-4,-1,0,1,4,6,8,9,10,12...},+,*) gyűrű (már ha az)
- vagyis Z\({primek}unio{-primek}) mármint prímek Z-ben:)
ebben pl 4 felbonthatatlan, és 6*8=48 4|48 de sem 6 sem 8 nem osztható 4-el vagyis 4 nem prím
ez jó?
-
Zsoldos #30 Paros szamok alatt mit ertesz? ...-6 -4 -2 0 2 4 6... valahogy igy? A "szokvanyos" (+, *) muveletekkel ez nem alkot euklideszi gyurut ezert nem definialhato sem a prim, sem a felbonthatatlan fogalma. Indoklas pl euklideszi gyuru egyik szukseges feltetele az egysegelem letezese, ebben a gyuruben pedig nincs. (def: H gyuru, e egysegelem, ha e E H, es minden a E H-re ae=a) Mivel egysegelem sincs, ezert egyseg sem (integritasi tartomanyban letezik egysegelem <=> letezik egyseg). Az egyseg defje egyebkent a egyseg H integritasi tartomanyban, ha minden x E H -re a|x , tehat minden mas szamnak osztoja. De mondjuk nem kell ennyire bizonygatni, konnyen lathato, hogy nincs olyan szam a paros szamok kozott, ami minden masiknak osztoja lenne, ezert egyseg sincs, ami ott szerepel a felbonthatatlan definiciojaban.
Az ember elso ranezesre azt mondana, hogy a 2 minden paros szamnak osztoja, ez az egesz szamok kozott igaz is, de a paros szamok kozott mar nem.. Pl 2 nem osztoja 6-nak, mivel nem letezik olyan xE{paros szamok} amire 2x=6. (az oszthatosag definicioja..) Ha kilepsz a megszokott Z-bol akkor semmi sem olyan egyszeru mint latszik, mindennek utana kell gondolni. -
Zsoldos #29 szoismetles :) -
Zsoldos #28 Hat mert masra nem is nagyon lehet, pl az oszthatosag is csak integritasi tartomanyban van ertelmezve. Ez a legaltalanosabb, ezert ez a hivatalos definicio. Ha egyszerusitett rendszeren dolgozol, akkor mar mast tetelt bizonyitasz szerintem, esetleg max otletet adhatnak az ilyesmik szerintem. -
7evenb #27 igaz, igaz!, és pl a páros számok körében a def szerint nincs is prím, csak felbonthatatlan:)
de azért a részemről maradnék Z-ben, ugyanis vannak olyan sturktúrák ahol nem teljesülnek a "hétköznapi" prímtételek:
maradékosztály gyűrűben véges sok prím van...
--------
bár érdekesek ezek is...lehet hogy a megoldatlan tételek vizsgálatát ilyen leegyszerűsített rendszereken kéne kezdeni?!
egyébként miért pont gyűrűn definiálod?
-
Zsoldos #26 Szoval amit te irtal az inkabb a felbonthatatlanok defjere hasonlit inkabb. Ha egesz szamokat nezzuk , vegulis ekvivalens, de nem csak az egesz szamok kozott leteznek primek, sokkal altalanosabb a fogalom. -
Zsoldos #25 Hat, nem tudom mennyire lesznek ismerosek a fogalmak, itt a definicio:
R euklideszi gyuru, E az egysegek halmaza (R* := R\{0} -> 0 itt a gyuru nullelemet jeloli)
a eleme R*\E prim, ha a|bc (b,c eleme R) eseten a|b vagy a|c.
a eleme R*\E pedig felbonthatatlan, ha a=bc (b,c eleme R) eseten b eleme E vagy c eleme E.
Az egesz szamok gyurujeben (Z, +, *) ez a ket halmaz epp egybeesik, de nem minden gyuruben van igy. -
Devla #24 Akkor valaki azt is bizonyítsa be, hogy végtelen sok prímszám van. Ez tényleg nagyon egyszerű. -
Devla #23 Arra a definícióra gondolsz, hogy ha p prím és p=n*m, akkor abból következik, hogy n=p vagy m=p? (Más megfogalmazásban: p prím, n|p és m|p => n=p vagy m=p) -
7evenb #22 bizony 
-
7evenb #21 Zsoldos:
mi a def? -
#20
nem ellenőrzéssel gondoltam, hanem ráérzéssel :)
ugyebár az idők során, osztáskor, szorzáskor találkozunk a számok többségével amik ezután valahogy "ismerősen" csengenek. a prímekkel viszont ritkábban találkozunk, ezért viszonylag könnyen fel lehet őket ismerni. :) -
#19
prím -
Zsoldos #18 Hat hogy ellenorizd, hogy van-e prim osztoja n szamnak, boven eleg gyok n -ig probalgatni (gondolom egyertelmu hogy miert), ezen belul is a primekkel. Tehat 200 alatti szam eseten max 8 osztast kell vegezned. Minel kisebb a szam annal konnyebb fejben megsaccolni. -
#17
A kocka első részében is a prím számokon alapult, hogy jó terembe mennek-e?
-
cyrus #16 nemfeltétlen.
167.
prím-e ? :O
-
#15
érdekesek ezek a prímszámok.
Amúgy megfigyeltétek már, hogy egy 1-től kb. 200-ig milyen könnyen megmondja az ember egy számról, hogy prím-e vagy sem? (gondolom mert kevesebbszer fordulnak elő a számítások során) -
#14
Szereted a matekot 
-
blackgamer #13 régen foglalkoztam prímszámkereső algoritmusokkal, persze amiket én találtam ki, mindig finomítottam rajta, és 486-os gépeken futtattuk
régi szép idők
-
Zsoldos #12 De nem is ez a definicioja a primszamoknak. -
ricky #11 :DDD én meg a komplex számokank!!! -
cyrus #10 ez kurvajó, én nyitok egy topikot a természetes számoknak ! ^.^
-
#9
Mi az a prímszám?! 
