Prost broj

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Lol... tamo se upravo i navodi ovaj algoritam koji sam ja prvi napisao . Jos sam malo razmisljao i definitivno ne moze drugacije nego ovako... Kvadratni koren nekog broja ti nista ne znaci posto proizvod bilo koja dva prosta broja da je novi broj koji je deljim samim sobom, jedinicom i samo jos sa ta dva prosta broja... Tako da ipak brute force nastupa na snagu .

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Za racunanje prostog broja ne postoji neka matematicka funkcija (bar je jos nisu pronasli). Ucili smo u srednjoj jednu funkciju (i dokazali da je tacna)... ne secam se tacno koji matematicar je pronasao, ali ta funkcija radi tacno samo za brojeve do 100... tako da brute force ne moze da se izbegne

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Najpoznatiji algoritam za proste brojeve je Eratostenovo sito! Radi na sledećem principu: Kad tražiš sve brojeve koji su prosti između 1 i n, prvo izbaciš sve brojeve koji su deljivi sa 2 osim 2, pa sve koji su deljivi sa 3 osim 3 i tako dalje... Ostaće ti samo prosti brojevi!

Imao sam i kod negde, ali ne mogu sad da nađem, potraži na Googlu, naći ćeš sigurno!

Evo, našao sam link na Wikipediji, pa pogledaj, možda ti bude jasnije nego moje objašnjenje!
[Link mogu videti samo ulogovani korisnici]

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Da, ali koliko se meni cini to je jos zahtevnije od ovog sto smo mi rekli... Ti u ovom algoritmu moras vise puta proci kroz 1 do n brojeva, do duse svaki put sa sve manje brojeva u nizu i da odbacujes brojeve, a u ovom nasem "algoritmu" imas samo jedan prolaz kako god okrenes...

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Ipak mislim da je ovaj algoritam brži. Pokušaj da izmeriš vreme izvršavanja programa za recimo n=1.000.000! Fazon je što kad program izbacuje brojeve iz niza ne kreće od sebe, nego svoje vrednosti na kvadrat! Na primer za 2 kreće od 4, za 3 od 9, za 5 od 25 jer su svi manji od vrednsti na kvadrat već izbačeni.

Koliko sam čitao, ovo je najbrži poznati algoritam za brojeve manje od 10.000.000, mada ni za veće brojeve nisam našao neki brži!

Čekaj, sad ću naći sajt, skoro sam ga gledao, imama ga u History-u verovatno...

Evo: [Link mogu videti samo ulogovani korisnici]
Tu imaš lepo i tačno napisanu brzinu algoritma!



poz

edit

Sad sam u stvari video da njemu treba samo da proveri da li je broj prost. U tom slučaju možda i jeste brži taj algoritam. ali ako mu trebaju svi prosti brojevi do nekog broja, onda je ovaj što sam napisao najbolji!

Nema veze, zatrebaće nekom!

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Eto mislim da taj brut nije toliko los....

Ima jedno ubrzanje stvar je sledeca ako hoces da ispisujes sve proste brojeve mozes prvo da testirs da li je kandidat da bude prost broj posto imaju neki tamo Mat fazoni .......

Stvar je sledeca svaki prosti broj veci od tri je oblika 6*n-1 ili 6*n+1....

Pa dakle ako hoces da ispitas da li je neki broj prost ispitas da li je toga oblika pa onda brute force samo stavi pretpostavku da je prvo prost i ono for simuliraj sa wile i kada vidis da jeste iskocis iz while a nakon toga ako jest boolean true onda je prost a ako nije onda je folse

HH

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

evo ovak... da li je broj prost i stampati proste brojeve do n
funkcija i program zgledaju ovako
function prost(n:integer):boolean; var p:boolean; i:integer; begin p:=true; for i:=2 to (n div2) do if n mod i=0 then p:=false prost:=p end; begin read(g); for i:=2 to g do if prost(i)=true then writeln(i); end.
jel to to?

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Malo cu vise da koda ubacim ali sta se sad tu moze.....

(*U programu*) i:=1; WHILE(i<=(n MOD 6))DO BEGIN       IF Prost(6*i-1) THEN              WRITELN(6*i-1);       IF (Prost(6*i+1) AND (n >= 6*i+1) THEN               WRITELN(6*i+1);       i:=i+1 end; (*Ide fubnkcija*) FUNCTION Prost(i:INTEGER):BOOLEAN;     VAR j : BOOLEAN;            Rezultat:BOOLEAN;     BEGIN            Rezultat := TRUE; j:=2;                        WHILE((j<(i MOD 2)) AND Rezultat) DO BEGIN                    IF ((i MOD j) = 0) THEN                         Rezultat := FALSE;                    i:= i+1            END;            Prost := Rezultat     END;

eto mislim i da bi malo mogao da ubrzam onaj dio j <(i MOD2) ide nesto sa korenom ili takvo sta slicno....

Inace ono sa Eratostenovim sitima nije lose al mislim da moras niz da imas u memoriji ili skup ako ides sa skupom zavisi koliko elemenata moze da istrpi masina pa to malo dodje kao neko malo ogranicenje..

HH

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Cini mi se da je ovo najbrze
program prostbroj; var prost : boolean;       i,n : integer; begin        readln(n);        prost := true;        if not (odd(n)) and (n<>2) then prost := false        else begin             i := 3;             while (i <= trunc(sqrt(n))) and prost do begin                     prost := n  mod i <> 0;                     i := i + 2;             end;        end;        if prost then writeln('Jeste') else writeln('Nije'); end.                     [/code]

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

ups mislim da u delfiju postoji vec ugradjena funkcija koja ispituje jel broj prost ili nije......