Zadatak: naci broj sa najvise delilaca

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

Pozdrav ljudi,idem na takmicenje iz infosa i ovaj zadatak me mucni nenormalno.

http://z-trening.com/tasks.php?show_task=5000000014&lang=rs

Nije problem uraditi ga vec vreme za koje racunar to odradi. Limit je 1 sekunda a mom programu je do 100 000 trebalo pola minuta. Sto znaci da bi mu do 2 milijarde trebalo nekoliko dana

Ima li neko mozda ideju kako ga resiti ?

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

Kako si ga uradio?
Prvo sto mi pada na pamet, kad trazis delilac kreces se do korena tog broja, ne moras dalje. Znatno ce ga ubrzati.

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

N1k0l4 ::Kako si ga uradio?
Prvo sto mi pada na pamet, kad trazis delilac kreces se do korena tog broja, ne moras dalje. Znatno ce ga ubrzati.

Pa prvo sam pesaka skroz,a posle mi je i to sa korenom palo na pamet

Ali je problem sto je max broj koji program treba da podrzi 2^31,a njegov koren je negde oko 60000. A opet do 60000 ne moze da se stigne "pesaka",deljenjem svakog od brojeva sa svim brojevima do njegove polovine :/

Tako da mislim da opet ne bi komp mogao da to odradi za 1 sekund

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

Vise bi mi pomoglo kad bi okacio kod ( ako nije problem ) pa da vidimo eventualno neke implementacije.
Da, 60 000 je veliki broj da bi se ispitali svi brojevi, verovatno ima neki fazon da se neki "preskoce"....

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

Ja inace slabo razumem takve zadatke, ali mi ne deluje da se to ne moze uraditi sa korenom vec treba podeliti ulazni broj sa 2.

Sa korenom bi za broj 100 bilo od 1 do 10, a 100 moze da se deli i sa 50. Dakle po meni treba od 1 do n/2.

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

Sasvim je dovoljno ici do korena, npr:
broj 100 je deljiv sa: 1,2,5,10,20,50,100
Koren iz 100 je 10. Ako se provere svi brojevi do 10, automatski se imaju i preostali brojevi. Ako je broj n deljiv sa m, onda je n deljiv i sa n/m. ( 100 je deljivo sa 2, ali je deljivo i sa brojem (100/2) tj. 50 ).

Sam pristup dolazenja do resenje je pogresan. Dve "For" petlje ugnjezdene jedna u drugu su veoma neefikasne, pogotovo ako se u jednoj pelji broji do 2^31 (2.147.483.648-), a u drugoj cak do 46.341.

Pitanje da li sama petlja koja broji do 2.147.483.648 moze da se izvrsi za manje od 1 sekunde. Ako se u nju doda joj jedna for petlja pa jos i operacije deljenja ili provere ostataka,... nema sanse ...

Probaj da nadjes neki drugi nacin za resenje problema. Na primer, mnozenjem prostih brojeva (2,3,5,7,11,13 ...) da dobijes sto manji broj koristeci sto vise prostih brojeva. ( npr broj 120 dobijas kao 2x2x2x3x5, ima cak 16 delilaca, (3+1)x(1+1)x(1+1)=4x2x2=16 , 3 dvojke, 1 trojka i jedna petica)

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

karlos ::broj 100 je deljiv sa: 1,2,5,10,20,50,100
Zaboravio si 4 i 25

karlos ::
Koren iz 100 je 10. Ako se provere svi brojevi do 10, automatski se imaju i preostali brojevi. Ako je broj n deljiv sa m, onda je n deljiv i sa n/m. ( 100 je deljivo sa 2, ali je deljivo i sa brojem (100/2) tj. 50 ).
Da, upravu si. Ako se ide od 1 do sqrt(100) tj. od 1 do 10 onda dobijes brojeve 1,2,4,5 i fale ti jos brojevi 20,25,50,100. Dakle uvek je isti broj delioca i samo treba pomnoziti sa dva, a sam broj dobijen iz korena (10) racunamo jednom.

Ali sigurno postoji bolji nacin jer kao sto kazes bice sporo.

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

Bone Collector ::karlos ::broj 100 je deljiv sa: 1,2,5,10,20,50,100
Zaboravio si 4 i 25
he he, ajd sto sam ja zaboravio, ali sto je racunar zaboravio na ih napise !!! (rezultate sam prepisao sa racunara, jedan IF uslov sam stavio na pogresno mesto, pa nije uzeo u obzir rezultat gde se mnozi dva puta isti prost broj 2x2=4 ).

Inace ovaj algoritam koji sam napravio je mnogo brzi. Jedino sto jos nisam isprobao za brojeve vece od 200000. Radi na principu mnozenja prostih brojeva, dok ne nadje broj koji ima najvise delilaca, a pri tome je najmanji sa toliko delilaca.

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

ja sam voljan da pomognem i bas me ovo zanima ali ja jos ne razumem zadatak.

tj zadatak kao i razumem ali mi nije jasan primer

tj onda sam dosao do zakljucka da ja nesto ne kontam u zadatku kad su mi resenja nelogicna...

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

Ovo ti moze pomoci: http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/divis2.html