[Bubba]

Autor hash

zvuci divno ali te ne razumijem bas

To je i bila osnovna predpostavka.

program pisem isto kao da pisem u c-u?nisam nikad nes tak radio u linuxu al znam neke osnove c-a, ugl sam radio u devc++

Na ovoj razini, okruzje u kojem radis je manje vise nebitno, jer nemas sistemske funkcije koje bi ti bile eventualno bitne, bar ne za neke "primitivne" izracune.

n@|N - sta ovo predstavlja? n element N ?

Da je n element iz skupa prirodnih brojeva.

tj treba mi nes ovak:

/snip

Ne bas.

Mlad si ti jos, nauciti ces, samo te zajebavam malo, cisto zato sto ti je Google nepoznanica.

No u stvari, u cemu je point. Prime95 je programcic koji trazi Mersenneove prime brojeve, koji odgovaraju zapisu 2^n-1. Vec smo rekli da ti brojevi uzimaju kao temelj predpostavku da je svaki n@|N, ako je 2^n-1 prost broj, onda i n prost broj. Dokaz bi isao otprilike ovako:

Pretpostavimo suprotno; 2^n-1 je prost a n slozen, tj. da postoje
x,y@|N, x>1, y>1 takvi da je n=x*y -> Tada se 2^n-1 moze zapisati kao:

2^n-1 = 2^(x*y)-1 = (2^x)^y-1 = (2^x-1)*(2^(x(y-1)) + 2^(x(y-2)) + ... + 2^x + 1)

odnosno, 2^n-1 se moze faktorizirati pa nije prost. Ovdje imamo kontradikciju s pocetnom tvrdnjom, pa zakljucujemo da ako je 2^n-1 prost, i n mora biti prost.

Sto nam omogucuje ovaj dokazcic? Pa umjesto da defiliramo sve brojeve iz N, mi uzimamo samo one proste i provjeravamo je li broj zaista prost. Prime, konkretno, koristi Lucas-Lehmerov test za provjeravanje je li 2^n-1 zaista prost broj.

jel ima neki jednostavan nacin da provjerim dal je broj prime ili moram dijeliti sa svim brojevima pa provjeravat dal je cjelobrojni ostatak nula za svako djeljenje?

Naravno da ima brzih metoda. Cak i ove primitivne se mogu ubrzati tako da provjeravas samo brojeve do sqrt(x) broja za kojeg smatras da je prime (a ne do x-1) te da izbacis sve parne djeljitelje osim broja dva. Kao sto gore rekoh, Prime koristi Lucas-Lehmerovu metodu za provjeravanje primea, a kako ona radi mozes naci na pregrst mjesta po internetu.

nekak mi se neda to sve radit sad.... ja bi radje gotovo rjesnje ako ima, moze i kod od prime95 pa mi onda kazete kak da to iskompajliram u linuxu

Ima, ima. Use the Google, Luke.