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

1. #include <cstdlib>
2. #include <iostream>
3. #include <cmath>
4.  
5. using namespace std;
6.  
7. long n;
8.  
9. int main(int argc, char *argv[])
10. {
11.     cin >> n;
12.    
13.     long a[int(sqrt(n))];
14.     int brojprostih = 0;
15.    
16.     for (long i=2; i<sqrt(n); i++)
17.     {
18.         bool prost = true;
19.         for (long j=0; j<=brojprostih && prost; j++)
20.         {
21.             if (i%a[j]==0) prost = false;
22.         }
23.        
24.         if (prost)
25.         {
26.            a[brojprostih] = i;
27.            brojprostih++;         
28.         }
29.     }
30.    
31.     long bnajvisedel = 0;
32.     int najvisedel = 0;
33.    
34.     for (int i=0; i<sqrt(n); i++)
35.     {
36.         int brdel = 0;
37.         for (int j=0;j<brojprostih && j<=i/2;j++)
38.         {
39.             if (i%j==0) brdel++;
40.         }
41.        
42.         if (brdel > najvisedel)
43.         {
44.            najvisedel = brdel;
45.            bnajvisedel = i;         
46.         }
47.     }
48.    
49.     najvisedel = (najvisedel + 1) * 2;
50.    
51.     cout << bnajvisedel << endl;
52.     cout << najvisedel << endl;*/
53.    
54.     system("PAUSE");
55.     return EXIT_SUCCESS;
56. }

• 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:

[Link mogu videti samo ulogovani korisnici] i [Link mogu videti samo ulogovani korisnici]

Kao i ove dve veoma interesantne teme:

[Link mogu videti samo ulogovani korisnici]
[Link mogu videti samo ulogovani korisnici]

Koliko vidim ovo je jedan od brzih algoritama: [Link mogu videti samo ulogovani korisnici]

(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):

0. function delioc(n){
1. maxfaktor=1
2. minbroj=1
3.    for(i=1; i<n; i++){
4.       for(j=1; j <= sqrt(i); j++){
5.          if(i % j == 0){
6.             a[b++]=j
7.             j==sqrt(i)?"":a[b++]=i/j
8.          }   
9.       }
10.       #printf("Delioci za %d su: \n", i)
11.       #for (k in a) { print a[k] }; printf("Broj delioca: %d\n", b); print "\n"
12.       if(maxfaktor<b && minbroj<i){
13.          maxfaktor=b
14.          minbroj=i;
15.       }delete a;b=0
16.  
17.    }
18.  
19. }
20. BEGIN{ delioc(ARGV[1])
21.    print "Minbroj: ", minbroj, " i Maxfaktor: ", maxfaktor
22. }

• 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.