icatalin

Suma diviziorilor unui numar | Metode eficiente

Oct 14th, 2016
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. //Metoda 1:
  2.  
  3. int main()
  4. {
  5.     int x,div;
  6.     long long S=0;
  7.  
  8.     cin>>x;
  9.  
  10.     for (div=1; div*div < x; div++)
  11.         if (x % div == 0)
  12.             S = S + div + x/div;
  13.  
  14.     if ( div * div == x)
  15.         S= S + div;
  16.  
  17.     cout<<S;
  18.  
  19.     return 0;
  20. }
  21.  
  22.  
  23.  
  24. //Metoda 2: (de prosti, facuta de mine: faci produsul sumelor geometrice a unor progresii date de factorii primi ai
  25. // numarului ). Metoda este, totusi, eficienta.
  26.  
  27. #include <iostream>
  28. #include <cmath>
  29.  
  30. using namespace std;
  31.  
  32. long long suma_geometrica(long long baza, long long exp)
  33. {
  34.     if (baza==1)
  35.         return (exp+1);
  36.  
  37.     long long s= (1- pow(baza,exp)*baza)/(1-baza);
  38.     return s;
  39. }
  40.  
  41. long long suma_divizori(long long x)
  42. {
  43.     long long div=2,p,S=1;
  44.  
  45.     while (x != 1)
  46.     {
  47.         p=0;
  48.  
  49.         while (x % div == 0)
  50.         {
  51.             x=x/div;
  52.             p++;
  53.         }
  54.  
  55.  
  56.  
  57.         if (p) {
  58.                 S=suma_geometrica(div,p)*S;
  59.                 //cout<<div<<" la puterea "<<p<<" ";
  60.             }
  61.  
  62.         div++;
  63.     }
  64.  
  65.     return S;
  66.  
  67. }
  68.  
  69. int main()
  70. {
  71.   long long x;
  72.   cin>>x;
  73.  
  74.   cout<<suma_divizori(x);
  75.  
  76.   return 0;
  77.  
  78. }
Advertisement
Add Comment
Please, Sign In to add comment