Zadatak: naci broj sa najvise delilaca

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

Napisano: 16 Apr 2010 0:09

Evo mog koda,koji je prvo previse komplikovan cini mi se,drugo ne radi,izbacuje mi gresku cim malo veci broj ubacim,a i ima problem neki sa velicinom ovog "a" arraya.

Evo koda,pa mozda ako neko ima ideje. Glup sam za ovo,sta cu XD

#include <cstdlib> #include <iostream> #include <cmath> using namespace std; long n; int main(int argc, char *argv[]) {     cin >> n;         long a[int(sqrt(n))];     int brojprostih = 0;         for (long i=2; i<sqrt(n); i++)     {         bool prost = true;         for (long j=0; j<=brojprostih && prost; j++)         {             if (i%a[j]==0) prost = false;         }                 if (prost)         {            a[brojprostih] = i;            brojprostih++;                  }     }         long bnajvisedel = 0;     int najvisedel = 0;         for (int i=0; i<sqrt(n); i++)     {         int brdel = 0;         for (int j=0;j<brojprostih && j<=i/2;j++)         {             if (i%j==0) brdel++;         }                 if (brdel > najvisedel)         {            najvisedel = brdel;            bnajvisedel = i;                  }     }         najvisedel = (najvisedel + 1) * 2;         cout << bnajvisedel << endl;     cout << najvisedel << endl;*/         system("PAUSE");     return EXIT_SUCCESS; }

Dopuna: 16 Apr 2010 0:10

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

Veceras cu to da pogledam,mozda mi da neku ideju

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

Izgleda da je karlos na dobrom putu. Necu se praviti da ovo razumem, ukljucio sam se u zadatak iz radoznalosti. Ipak, izgleda da je ovo veoma opsirna tema sa dosta opcija i mnogo mozganja:

http://en.wikipedia.org/wiki/Integer_factorization i http://en.wikipedia.org/wiki/Divisor_function

Kao i ove dve veoma interesantne teme:

http://stackoverflow.com/questions/171765/what-is-.....f-a-number
http://stackoverflow.com/questions/110344/algorith.....ven-number

Koliko vidim ovo je jedan od brzih algoritama: http://cr.yp.to/primegen.html

(coveka znam kao autora izvanrednog djbdns softvera)

A evo i skripte (da skripte ) koju sam ja uspeo da sastavim. Napisana je u awk-u, i za 100.000 brojeva joj treba nesto vise od 14 sec na Celeronu, dok za milion brojeva "krlja" oko 7 minuta. Nisam isprobavao koje je vreme kad bi se prebacilo u C, ali ocekujem dobro poboljsanje. Mozda ti neki deo nje bude od pomoci (sintaksa je slicna C-u):

function delioc(n){ maxfaktor=1 minbroj=1    for(i=1; i<n; i++){       for(j=1; j <= sqrt(i); j++){          if(i % j == 0){             a[b++]=j             j==sqrt(i)?"":a[b++]=i/j          }          }       #printf("Delioci za %d su: \n", i)       #for (k in a) { print a[k] }; printf("Broj delioca: %d\n", b); print "\n"       if(maxfaktor<b && minbroj<i){          maxfaktor=b          minbroj=i;       }delete a;b=0    } } BEGIN{ delioc(ARGV[1])    print "Minbroj: ", minbroj, " i Maxfaktor: ", maxfaktor }
Postoje neke varijante izuzimanja odredjenih brojeva i slicno, ali to vec prevazilazi moju zelju za matematikom. Sve najbolje i nadam se da ce ti neki od ovih linkova pomoci.

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

Da li je neko slucajno resio ovaj zadatak?I mene muci vreme,kod mi je ispravan.