U nedostatku boljeg "foldera" (ili kako se vec kaze), odlicio sam postavit pitanje ovdje.
Zanima me kolika je slozenost Eratostenovog sita. Tocnije: Za zadani broj n, kolika je slozenost nalazenja svih prostih brojeva od 1 do n pomocu spomenutog algoritma.
Do cega smo dosli:
Definitivno je bolje od n^2 i losije od n. Zbog Gaussove aproksimacije o "gustoci" prostih brojeva, izgleda da je slozenost bolja ili jednaka n*ln(n) (jer za svaki prosti broj moramo proci po polju) sto je jednako n*lg(n).
Ali za vece proste brojeve, brze prolazimo po polju i ne znam spusta li to slozenost algoritma i ako da, moze li se to nekako aproksimirati.
Hvala.
U nedostatku boljeg "foldera" (ili kako se vec kaze), odlicio sam postavit pitanje ovdje.
Zanima me kolika je slozenost Eratostenovog sita. Tocnije: Za zadani broj n, kolika je slozenost nalazenja svih prostih brojeva od 1 do n pomocu spomenutog algoritma.
Do cega smo dosli:
Definitivno je bolje od n^2 i losije od n. Zbog Gaussove aproksimacije o "gustoci" prostih brojeva, izgleda da je slozenost bolja ili jednaka n*ln(n) (jer za svaki prosti broj moramo proci po polju) sto je jednako n*lg(n).
Ali za vece proste brojeve, brze prolazimo po polju i ne znam spusta li to slozenost algoritma i ako da, moze li se to nekako aproksimirati.
Hvala.
_________________
Sin:"Tata, šta je to rekurzija?"
Otac:"Rekurzija."
