Divizori

[•tErMy]

    Salut! 
    Am dat peste o problema care necesita numarul de divizori al unui numar mare ( maxim 2 miliarde ).
Metoda clasica ( for (i=2; i<=n/2; i++) if (n%i==0) nrdivizori++ ) depaseste timpul . M-am uitat pe indicatii si acolo scria ca este necesar un program care genereaza numere prime si descompun nr in numere prime.. insa fac informatica doar de aproximativ 6 luni si nu stiu sa fac prea bine astea .
    Ceea ce va rog este sa imi aratati un model de algoritm care afla numarul de divizori al unui numar sau sa ma ajutati sa inteleg metoda pe care am pomenit-o mai sus pentru ca la nivelul la care sunt acum ma depaseste.
    Multumesc !

[•Florian]

Pai..sa presupunem ca ai numerele prime pana la 2 miliarde in vectorul a[] (acestea sunt aproximativ in nr de 45.000 cred]. [Le poti genera prin eratostene -vezi la articolele de pe site, sau daca nu, metoda clasica].
Formula pt numarul divizorilor este: nr_divizori= (1+r1)*(1+r2)* ... (1+rk), unde r1,r2,..rk sunt puterile la care apar factorii primi p1,p2, ... respectiv, pk, in descompunerea lui N [unde N=nr al carui nr de divizori tre sa il afli].
Ideea e, ca la factorizarea [descompunerea] lui N sa vezi de cate ori se imparte N la fiecare din elementele vectorului a[], astfel factorizarea fiind mult mai rapida, si capatand complexitate O(sqrt(N)).

ps: Daca nu stii sa implementezi, da`mi un pm cu id-ul de messenger, si te ajut cu placere. 

[•sims_gl]

Florian, ai o mica greseala. Numerele prime pana la 2 miliarde sunt mult mai multe decat 45000 [si chiar daca ar fi doar atatea, pana si ciurul lui eratostene are complexitate O(NlogN) si memorie O(N), si nu s-ar incadra in nici una]. Numai ca le folosesti doar pe cele pana la sqrt(N) [adik radical din N, Andrei, daca nu stiai ce inseamna]. Si intradevar sqrt(N) = 45000, iar numerele prime sunt mai putine decat atat. Ideea e ca un numar N poate avea cel mult un divizor prim mai mare decat radicalul lui [daca vrei o sa incerc sa-ti si demonstrez]. Asa ca imparti N la fiecare numar prim din cele aflate si afli puterile la care se referea Florian, si daca dupa impartiri N > 1, atunci N este numar prim si are puterea 1.
Andrei, sper ca ai inteles! Daca mai ai intrebari, o sa-ti raspund cu placere.

[•Prostu]

Nu este nevoie de ciurul lui Eratostene. Este de ajuns sa numeri de 2 ori fiecare divizor pana la sqrt(N), avand grija sa scazi 1 daca numarul e patrat perfect.
Fie N, numarul dat si d un divizor al sau, atunci si N / d este divizor al lui N. Pentru a nu numara divizorii de 2 ori, vom pune constrangerea ca d < N / d, care este echivalent cu d < sqrt(N).

Cod:

stop = sqrt(N);
for (i = 2; i <= stop; ++i)
    if (N % i == 0) nrdivizori += 2;
if (stop * stop == N) --nrdivizori;

[•wefgef]

Prostule, ai uitat sa numeri divizorii 1 si N.

[•Prostu]

Din postul lui initial am inteles ca vrea numai divizorii proprii, [for (i = 2...].

[•Florian]

Prostule, ai uitat sa numeri divizorii 1 si N.

Ce fain suna. 

[•tErMy]

in problema am de aflat numarul de divizori al tuturor numerelor din intervalul [a;b] ( b-a<= 10.000 si valoarea maxima a lui b e de 2 miliarde ) si imi trebuie un algoritm care nu executa multe oeratii pentru fiecare numar...
Am vorbit cu Florian pe mess si ma ajutat la segventa de aflat numarul de divizori a unui numar folosind numerele prime si puterea la care se gasesc ele ( tin sa ii multumesc pe aceasta cale ), insa pentru aceasta am nevoie de un vector in care se afla toate numerle prime mai mici sau egale cu b, ceea ce nu l-am mai intrebat crezand ca stiu sa fac asta..
Am facut algoritmul prin care generez numerele prime , merge , dar depaseste timpu 

Cod:

unsigned long prim(unsigned long x)
          {if(x==1)return 0;
           if (x==2) return 1;
           if (x%2==0) return 0;
          for(unsigned long i=3;i<=x/2;i=i+2)
	       if(x%i==0)return 0;
          return 1;}    // functia pt aflat numere prime
.............................
p[1]=2;
 k=2;
 for(j=3; j<=b; j=j+2)
    if (prim(j))
      {p[k]=j;
       k++;}  //inserarea in vector a numerelor prime

O sa incerc metoda lui Stefan si revin 

[•skyel]

dar, stii ca fiecare problema de pe infoarena are topic separat in forum, nu? Nu stiu de ce dar am impresia ca te chinui sa faci problema Maxd.

[•wefgef]

Pentru a rezolva maxd e de ajuns sa parcurgi toate numerele de la a la b si sa numeri cati divizori are fiecare folosind algorimtul postat de Prostu. Nu trebuie sa te chinui in halul asta .

[•tErMy]

dar, stii ca fiecare problema de pe infoarena are topic separat in forum, nu? Nu stiu de ce dar am impresia ca te chinui sa faci problema Maxd.

da ... acea problema incercam sa o rezolv. Imi pare rau daca am gresit facand topicul asta dar sunt nou pe aici si nu am stiut    .
am incercat cu algoritmul postat de el dar depaseste timpul la 3 din teste si da rezuktat incorect la celelalte 7.
Asta este sursa.. http://infoarena.ro/job_detail/122745?action=download

[•wefgef]

Ai acolo if (n%j)... trebuie if (i%j).

Am schimbat asta si am obtinut urmatoarele rezultate: http://infoarena.ro/job_detail/122750

Daca optimizezi putin iei 100.

[•tErMy]

wow ... neatentia    o sa incerc sa optimizez si sa iau 100 puncte.
Multumesc mult tutoror pentru ajutor !