pra števila..

Če bi obstajala funkcija za praštevila, bi bilo iskanje le-teh veliko lažje, se ti ne zdi? Obstajajo samo algoritmi, ki ti za določeno število izračunajo, če je praštevilo oz. ti poiščejo vsa praštevila na določenem intervalu.

BTW: 27 ni praštevilo.

ja, pa res ni 27 :) 27:9=3

mod je ostanek po deljenju

signum je pa 1, če je število pozitivno in 0, če je 0. Pa seveda -1, če je negativno.

zigam - kok si star?

Itak me pa zanima, kdo je to funkcijo sploh poznal.

14-1=13

1*2*3*4*5*6*7*8*9*10*11*12*13=6227020800

6227020800+1=6227020801

6227020801/14 = 444787200,071428

Ne deli se brez ostanka, ali kar je isto, mod 14 ni 0 - torej 14 ni praštevilo.

Zato, ker ni ostanka pri deljenju :)

aja, pol sm pa bil že mal zaspan nism vidu da ni blo ostanka :)
a to je pol to?
a se da komu še nardit to po tem k je thomas napisu:
F(N) = Signum(((N-1)!+1) mod N)
za številko 7 pa 6

dooooooo velik??
a je težko za 6 pa 7 zračunat??? po tisti formuli?

ej Thomas, a mi lah po tem F(N) = Signum(((N-1)!+1) mod N)
zračunaš za 7 pa 6 na ta dolg način :) za vsak korak posebi no pa še eno vprašanje? a kdo ve kje bi dubu program k mi lah zračuna na tut več k 1000 decimalk natančn.. no da bi določu do kok natančn naj ti zračuna(pa če se da neomejeno)

Zigam, če ne gre drugače, na malce boljšem kalkulatorju preprosto izračunaš, potem pa slediš postopku:

napišeš na list papirja število z vsemi decimalkami, ki jih vidiš
zmnožiš s 1000,
odšteješ celi del števila.

ponavljaš do takrat, ko imaš dovolj decimalk :] tole
pomnožiš,
odšteješ celi del,
pripišeš na list zadnje 3 decimalke
>> ponavljaj.

... V sili ...

Uuu, Thomas, dobra finta tole. Morda veš kdo se jo je spomnil oz. kako so jo odkrili?

Thomas: to so bile neke osmorazredne finte. S Primozem sva se nekaj igrala, tako da je v Delphiju spisal program, ki je iskal vsa praštevila od 1 do 4 mrd ter jih zapisoval v neko datoteko. Dost dobra zadeva, delovala ko hudič na Celeronu 266. Sem žrtvoval cel gigabajt (leta 1998 je bilo to VELIKO) diska za vsa praštevila do 4 mrd. Malo me nostalgija daje, kaj naj rečem .

auč.

resnično upam, da je ta punca sedaj tvoja žena.

Heee, hudo

To gre definitivno na mojo steno!

Jasno, s taprvo, ki je bla sposobna seštrikat pulover v obliki Eratostenovega sita sem se oženu.

Car si, Thomas!

Thomas vprašanje zate:

The 2002 Nevanlinna Prize -> Madhu Sudan

Dobil je nagrado za nov algoritem v iskanju praštevil.

Ker sem to zgolj slišal, me zanima, če lahko poveš kaj več o tem (o algoritmu)?




PS. Sem poskusil poiskate v googlu pa na žalost ne ločim trave od plevela. Tako, da je iskanje splavalo po vodi.

najvecje prastevilo ki so ga odkrili je blo 2^832455 - 1. Neki tazga, ne vem če je čist točn. Kul a ne.?

jst sm v VB-ju napisau program v katerga upises cifro in ti napiše če je praštevilo s to kodo, če zna kdo prebrat

Dim y As Double, x As Double, z As Double, rez As Double
x = Text1.Text
y = 1
For i = 1 To x - 1
y = y * i
Next i
Text2.Text = y
z = y + 1
rez = z Mod x
Text3.Text = rez
If rez = 0 Then
Label1.Caption = "To JE praštevilo"
Else
Label1.Caption = "To ni praštevilo"
End If

edina slabost je da ne mors računat s števili večjimi kot okoli 100.

mogoče kdo ve kako bi naredu, da bi mi delalo za vsa števila oz. vsaj do 1000?

Lani. 2001.



See?

Guglmajstr.

ej P_Nut , a mi lah na mail pošleš original *vbp al krkol maš, bom pogledu če se bom kej znajdu ,, mogoče bom js odkril nov algoritm, k nam mogu zaspat, sm že par stvari ugotovu sam, problem je bil edin, k je blo to že zdavnej znano , sm mislu da je največje praštevilo mal manjše npr. okol 1 miljarde, pa je očitno večje ,pa P_Nut če se ti bo dal, da ti nav treba gledat posebi maila: zigamakuc@hotmail.com

CHAOS - I'll do my best!

6. avgusta letos so Agrawal, Kayal in Saxena iz indijskega inštituta za tehnologijo v Kanpurju, objavili nov algoritem za določanje tega, če je število praštevilo ali ne.

Posebnost tega algoritma je v tem, da je njegova časovna odvisnost teoretično sorazmerna z dvanajsto potenco logaritma iz števla. V praksi se pa izkaže, da le s šesto.

Če bi pa dokazali še nekaj dodatnih izrekov, ki jih imajo že na ponku, bi bila koračna odvisnost algoritma sorazmerna s tretjo potenco logaritma iz števila.

Kar je daleč bolje kot formula, ki sem jo navedel više zgoraj, kjer je koračna odvisnost transpolinomska - NP.

Algoritem:

if N = a^b output COMPOSITE

r=2

while (r < n) {

if ( gcd(n,r) != 1 ) output COMPOSITE // gdc je največji skupni deljitelj

if (r is prime) let q be the largest prime factor of r-1

if ((q > 4*sqrt(r)*log(n)) and (n^(r-1)/q) != 1 mod r) break;





r=r+1;

}

for a=1 to 2*sqrt(r)*log(n)

if (x - a)ⁿ != (x - a)*((x^r-1 mod n) output COMPOSITE

output PRIME;


End of algoritem.

Zdej hec je v tem, da se tisti break v while zanki relativno zelo hitro zgodi in da mora steči samo še spodnja zanka, ki teče do zgoraj v while zanki izračunanega r.

Vse skupaj pa temelji na probabilističnem testiranju števil za praštevila, v katerega se uspešno poglablja Mr. Sudan.



Any questions, anybody?

To je algoritem, ni ravno program. Program rabi več vrstic.

> if (r is prime) let q be the largest prime factor of r-1

Če je r=101 potem naj bo q enak 5. Torej največje praštevilo, ki deli 100.

To je treba zračunat s programom.

Potem pa preveriti pogoj:

> if ((q > 4*sqrt(r)*log(n)) and (n(r-1)/q) != 1 mod r) break;

Če je izpolnjeno, smo iz while zanke že ven.

V tazadnji for zanki, pa mora x izpolniti vse vrednosti do a.

V bistvu je dvojna for zanka v programu. Za algoritem je dosti napisano.

Bom mogoče napisal še točen program. Samo komu ne bo toliko razumljiv kot je tole.

Thomas:

Funkcija je:

F(N) = Signum(((N-1)!+1) mod N)

Signum od 0 je 0, od večjih števil pa 1.

Za praštevila da F(N) = 0. Za ostale da 1.

F(5)=Signum(((5-1)!+1) mod 5)

To je 0, torej 5 je praševilo.

Saj funkcije Signum sploh ne potrebujemo. Lahko napišem:
F(N) = ((N-1)!+1) mod N

potem pa:
if(F(N) = 0) then
N je praštevilo
else
N ni praštevilo

Torej: Za praštevila da F(N) = 0. Za ostale da != 0.

P.S.: Tvoj trenutni podpis mi je zlo všeč! :)

Čist tko me zanima - a je kdo kej imel od tegale?

Kaj če do konca napišem progija za določevanje sestavljenosti?

Ga bodo bwane gor uzele? Ga bo ljudstvo dol jemalo?

Ja po zgornjem algoritmu bom napisal program, za hitro določevanje, če je število pra ali ni pra.

Pol pa, kdor si ga bo hotu, ga bo lahko dol vzel iz slotecha. Če na slotechu bo, seveda.

Jaz nestrpno pričakujem source.