|
Poslao: 20 Dec 2005 01:20
|
offline
- Strog
- Stručni saradnik
Web programiranje
- Bojan Kopanja
- Web & Mobile developer @ ZeusSoftware
- Pridružio: 26 Jul 2003
- Poruke: 2597
- Gde živiš: Stara Pazova
|
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 .
|
|
|
|
|
Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
|
|
|
Poslao: 20 Dec 2005 11:54
|
offline
- Srki_82
- Moderator foruma
- Srđan Tot
- Am I evil? I am man, yes I am.
- Pridružio: 12 Jul 2005
- Poruke: 2483
- Gde živiš: Ljubljana
|
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 
|
|
|
|
|
|
|
Poslao: 20 Dec 2005 16:13
|
offline
- Pridružio: 23 Jan 2004
- Poruke: 43
|
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!
en.wikipedia.org/wiki/Sieve_of_Eratosthenes
|
|
|
|
|
|
|
Poslao: 20 Dec 2005 18:17
|
offline
- Strog
- Stručni saradnik
Web programiranje
- Bojan Kopanja
- Web & Mobile developer @ ZeusSoftware
- Pridružio: 26 Jul 2003
- Poruke: 2597
- Gde živiš: Stara Pazova
|
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...
|
|
|
|
|
|
|
Poslao: 20 Dec 2005 19:16
|
offline
- Pridružio: 23 Jan 2004
- Poruke: 43
|
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: primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes
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!
|
|
|
|
|
|
|
Poslao: 17 Avg 2006 10:54
|
offline
- Pridružio: 11 Jun 2006
- Poruke: 94
|
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
|
|
|
|
|
|
|
Poslao: 19 Avg 2006 14:22
|
offline
- N1k0l4
- Prijatelj foruma
- Pridružio: 06 Sep 2005
- Poruke: 3800
- Gde živiš: Beograd
|
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?
|
|
|
|
|
|
|
Poslao: 22 Avg 2006 10:31
|
offline
- Pridružio: 11 Jun 2006
- Poruke: 94
|
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
|
|
|
|
|
|
|
Poslao: 25 Dec 2007 23:01
|
offline
- boris4
- Novi MyCity građanin
- Pridružio: 24 Dec 2007
- Poruke: 6
|
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]
|
|
|
|
|
|
|
Poslao: 28 Dec 2007 22:15
|
offline
- Pridružio: 11 Jun 2006
- Poruke: 94
|
ups mislim da u delfiju postoji vec ugradjena funkcija koja ispituje jel broj prost ili nije......
|
|
|
|
|
|
