Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Razmatranje slozenosti Eratostenovog sita

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - opušteno -> Bućkuriš
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
ZELENIZUBNAPLANETIDO
SADE
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 04. 03. 2004. (19:56:15)
Postovi: (54F)16
Sarma = la pohva - posuda
7 = 12 - 5
Lokacija: hm?
PostPostano: 12:57 pet, 26. 3. 2004    Naslov: Razmatranje slozenosti Eratostenovog sita Citirajte i odgovorite
Malko mi fali teorije vezane uz asimptotiku, pa me zanima:
1) slozenost algoritma Eratostenovog sita (za prvih n prirodnih brojeva)
2) dokaz :)

3) dok sam gruntao o tome, palo mi je napamet slijedece pitanje:
postoje razlicite procjene "brojnosti" prim brojeva medju prvih n prim brojeva (hardy&co), ali.. Ako bi sproveli nepotpuno eratostenovo sito do broja m>n. Krizali smo prim brojeve i prestali smo ih traziti kad smo dosli do broja n. Ako je m>n, koliko je cca ostalo "neprekrizenih" brojeva (izmedju n i m ukljucno), i koliko je od njih (cca) prim brojeva?
a) obrazlozenje, dokaz?
b) jos bolje :) uput na literaturu :)
Malko mi fali teorije vezane uz asimptotiku, pa me zanima:
1) slozenost algoritma Eratostenovog sita (za prvih n prirodnih brojeva)
2) dokaz Smile

3) dok sam gruntao o tome, palo mi je napamet slijedece pitanje:
postoje razlicite procjene "brojnosti" prim brojeva medju prvih n prim brojeva (hardy&co), ali.. Ako bi sproveli nepotpuno eratostenovo sito do broja m>n. Krizali smo prim brojeve i prestali smo ih traziti kad smo dosli do broja n. Ako je m>n, koliko je cca ostalo "neprekrizenih" brojeva (izmedju n i m ukljucno), i koliko je od njih (cca) prim brojeva?
a) obrazlozenje, dokaz?
b) jos bolje Smile uput na literaturu Smile



_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk Wink
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
krcko
Forumaš nagrađen za životno djelo
Forumaš nagrađen za životno djelo


Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
Sarma = la pohva - posuda
655 = 759 - 104
PostPostano: 23:33 pet, 26. 3. 2004    Naslov: Citirajte i odgovorite
Hmm, jesi ovo namjerno stavio u forum gdje duje (mozda) nece vidjeti? :-k
Hmm, jesi ovo namjerno stavio u forum gdje duje (mozda) nece vidjeti? Think



_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
ZELENIZUBNAPLANETIDO
SADE
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 04. 03. 2004. (19:56:15)
Postovi: (54F)16
Sarma = la pohva - posuda
7 = 12 - 5
Lokacija: hm?
PostPostano: 3:25 sub, 27. 3. 2004    Naslov: Citirajte i odgovorite
[quote="krcko"]Hmm, jesi ovo namjerno stavio u forum gdje duje (mozda) nece vidjeti? :-k[/quote]
Pa... Nisam :D ali nisam znao pod koji kolegij da ga smjestim...



[color=darkred][b]Admin (vsego) edit:[/b] Ono sto ne znas kud spada, stavis u [i]Cumez[/i]. :) Sad cu ja to premjestiti... 8)
(Just for the record: bilo je u [i]Biserima[/i])[/color]
krcko (napisa):
Hmm, jesi ovo namjerno stavio u forum gdje duje (mozda) nece vidjeti? Think

Pa... Nisam Very Happy ali nisam znao pod koji kolegij da ga smjestim...



Admin (vsego) edit: Ono sto ne znas kud spada, stavis u Cumez. Smile Sad cu ja to premjestiti... Cool
(Just for the record: bilo je u Biserima)



_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk Wink
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
duje
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: muško
Sarma = la pohva - posuda
338 = 339 - 1
PostPostano: 7:10 sub, 27. 3. 2004    Naslov: Citirajte i odgovorite
[quote]
1) slozenost algoritma Eratostenovog sita (za prvih n prirodnih brojeva)
2) dokaz
[/quote]

Oznacimo sa pi(x) broj prostih brojeva manjih ili jednakih x.
Tada je pi(x) asimptostski jednako x/ln(x), tj.
pi(x)*ln(x)/x --> 1 kada x --> beskonacno.
To znaci da je broj prolazaka kroz listu u Eratostenovom situ,
a to je broj prostih brojeva do sqrt(n), priblizno jednak
2*sqrt(n)/ln(n).

Ocijenimo sada broj aritmetickih operacija u Eratostenovom situ.
U prolasku kroz listu koji odgovara prostom broju p,
precrtavaju se (ili na njihovim lokacijama se 1 pretvara u 0)
brojevi p,2p,3p, ... sve do n. Dakle, trebamo [n/p] zbrajanja.
Prema tome, ukupan broj zbrajanja mozemo ocijeniti sa
n*(1/2+1/3+1/5+1/7+...) .
U zagradi je suma reciprocnih vrijednosti prostih brojeva
manjih od sqrt(n). Poznato je da je velicina asimptotski jednaka
ln(ln(n)). Dakle, sve u svemu imamo oko n*ln(ln(n)) zbrajanja.
Znaci, slozenost je O(n*ln(n)*ln(ln(n))) bitnih operacija
(i O(n) memorijskog prostora).
[quote]
3) dok sam gruntao o tome, palo mi je napamet slijedece pitanje:
postoje razlicite procjene "brojnosti" prim brojeva medju prvih n prim brojeva (hardy&co)
[/quote]

Ne znam na sto se tocno misli pod "razlicite procjene brojnosti".
Gore spomenuti rezultat pi(x) ~ x/ln(x) je dokazan prije stotinjak
godina (Hadamard i de la Vallee Poussin). Jos bolja aproksimacija
je pomocu funkcije li(x) koja se definira kao integral od 2 do x
od 1/ln(t) dt. Lako se vidi (parcijalnom integracijom ili
L'Hopitalovim pravilom) da je li(x) ~ x/ln(x).
Postoje razliciti rezultati i slutnje vezane za procjenu razlike
|pi(x) - li(x)|. Riemannova hipoteza povlaci (zapravo je ekvivalentna)
da je |pi(x) - li(x)| = O(sqrt(x)*ln(x)).

[quote]
Ako bi sproveli nepotpuno eratostenovo sito do broja m>n. Krizali smo prim brojeve i prestali smo ih traziti kad smo dosli do broja n. Ako je m>n, koliko je cca ostalo "neprekrizenih" brojeva (izmedju n i m ukljucno), i koliko je od njih (cca) prim brojeva?
a) obrazlozenje, dokaz?
b) jos bolje uput na literaturu
[/quote]

Ovako "odoka" bih rekao da je "neprekrizenih" ostalo cca
c*m/ln(n), gdje je c neka konstanta.

Za literaturu preporucam
R. Crandall, C. Pomerance: "Prime Numbers: A Computational
Perspective", Springer-Verlag, 2001.
Citat:

1) slozenost algoritma Eratostenovog sita (za prvih n prirodnih brojeva)
2) dokaz


Oznacimo sa pi(x) broj prostih brojeva manjih ili jednakih x.
Tada je pi(x) asimptostski jednako x/ln(x), tj.
pi(x)*ln(x)/x → 1 kada x → beskonacno.
To znaci da je broj prolazaka kroz listu u Eratostenovom situ,
a to je broj prostih brojeva do sqrt(n), priblizno jednak
2*sqrt(n)/ln(n).

Ocijenimo sada broj aritmetickih operacija u Eratostenovom situ.
U prolasku kroz listu koji odgovara prostom broju p,
precrtavaju se (ili na njihovim lokacijama se 1 pretvara u 0)
brojevi p,2p,3p, ... sve do n. Dakle, trebamo [n/p] zbrajanja.
Prema tome, ukupan broj zbrajanja mozemo ocijeniti sa
n*(1/2+1/3+1/5+1/7+...) .
U zagradi je suma reciprocnih vrijednosti prostih brojeva
manjih od sqrt(n). Poznato je da je velicina asimptotski jednaka
ln(ln(n)). Dakle, sve u svemu imamo oko n*ln(ln(n)) zbrajanja.
Znaci, slozenost je O(n*ln(n)*ln(ln(n))) bitnih operacija
(i O(n) memorijskog prostora).
Citat:

3) dok sam gruntao o tome, palo mi je napamet slijedece pitanje:
postoje razlicite procjene "brojnosti" prim brojeva medju prvih n prim brojeva (hardy&co)


Ne znam na sto se tocno misli pod "razlicite procjene brojnosti".
Gore spomenuti rezultat pi(x) ~ x/ln(x) je dokazan prije stotinjak
godina (Hadamard i de la Vallee Poussin). Jos bolja aproksimacija
je pomocu funkcije li(x) koja se definira kao integral od 2 do x
od 1/ln(t) dt. Lako se vidi (parcijalnom integracijom ili
L'Hopitalovim pravilom) da je li(x) ~ x/ln(x).
Postoje razliciti rezultati i slutnje vezane za procjenu razlike
|pi(x) - li(x)|. Riemannova hipoteza povlaci (zapravo je ekvivalentna)
da je |pi(x) - li(x)| = O(sqrt(x)*ln(x)).

Citat:

Ako bi sproveli nepotpuno eratostenovo sito do broja m>n. Krizali smo prim brojeve i prestali smo ih traziti kad smo dosli do broja n. Ako je m>n, koliko je cca ostalo "neprekrizenih" brojeva (izmedju n i m ukljucno), i koliko je od njih (cca) prim brojeva?
a) obrazlozenje, dokaz?
b) jos bolje uput na literaturu


Ovako "odoka" bih rekao da je "neprekrizenih" ostalo cca
c*m/ln(n), gdje je c neka konstanta.

Za literaturu preporucam
R. Crandall, C. Pomerance: "Prime Numbers: A Computational
Perspective", Springer-Verlag, 2001.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
ZELENIZUBNAPLANETIDO
SADE
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 04. 03. 2004. (19:56:15)
Postovi: (54F)16
Sarma = la pohva - posuda
7 = 12 - 5
Lokacija: hm?
PostPostano: 18:13 sub, 27. 3. 2004    Naslov: Citirajte i odgovorite
Hm Thnx :D

progruntam ja to jos malo... :)
Hm Thnx Very Happy

progruntam ja to jos malo... Smile



_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk Wink
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - opušteno -> Bućkuriš Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan