CODEWITHSUNDEEP
c++algorithm
tango
tango

Reputation: 79

Implementation of Sum of divisor algorithm in c++

I was trying to implement the sum of divisors algorithm in c++ i.e.,

Let n = p1^a1 * p2^a2 * .... * pk^ak

Then

σ(n) = ( (p1^(a1+1) - 1) / (p1-1) ) * ( (p2^(a2+1) - 1) / (p2-1) ) * ... * ( (pk^(ak+1) - 1) / (pk-1) )

The function for prime factorization that pushes factor in a vector<int> p

void primeFactors(int n)
{
    while (n%2 == 0)
    {
        p.push_back(2);
        n = n/2;
    }
    for (ull i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
            p.push_back(i);
            n = n/i;
        }
    }
    if (n > 2)
        p.push_back(n);
}

Then I create a copy of vector<int> p in vector<int> pk as vector<int> pk(p) and do following to have only unique elements in p.

auto it = unique(p.begin(),p.end());
 p.resize(distance(p.begin(),it) );

Now the final to get sum as per the formula:

for(int i=0;i<p.size();i++){
        sum *= (pow(p[i],count(pk.begin(), pk.end(), p[i]))-1)/(p[i]-1);
    }

The above implemention is wrong as I am not getting correct output. Where am I making a mistake? Is their a better method for implementing it?

Upvotes: 2

Views: 245

Answers (1)

AKJ88
AKJ88

Reputation: 733

Your final loop for calculating the result is pi^ai instead of pi^(ai+1). Change it to this:

for (int i = 0; i < p.size(); i++){
    sum *= (pow(p[i], count(pk.begin(), pk.end(), p[i]) + 1) - 1) / (p[i] - 1);
}

One more thing, instead of using vectors and using unique and count you can simply use a map<int, int> and instead of getting the number of occurrences of each prime number in O(n) get it in O(lgn) like this:

void primeFactors(int n, map<int, int> &facs){
    facs.clear();
    for (long long p = 2; p*p <= n; p++){
        while (n%p == 0){
            facs[p] ++;
            n /= p;
        }
    }
    if (n > 1)
        facs[n] = 1;
}

long long getRes(map<int, int> &facs){
    long long t, res = 1;
    for (auto it = facs.begin(); it != facs.end(); ++it){
        t = pow(it->first, it->second + 1) - 1;
        t /= (it->first - 1);
        res *= t;
    }
    return res;
}

In the above code I also used pow function for calculating the result. We can eliminate this function by storing power values instead of count in the map, like this:

void primeFactors(int n, map<int, long long> &facs){
    facs.clear();
    for (long long p = 2; p*p <= n; p++){
        while (n%p == 0){
            if (facs.count(p))//this way we can save pi^(ai+1) instead of counting prime numbers
                facs[p] *= p;
            else
                facs[p] = p*p;
            n /= p;
        }
    }
    if (n > 1)
        facs[n] = n*n;
}

long long getRes(map<int, long long> &facs){
    long long t, res = 1;
    for (auto it = facs.begin(); it != facs.end(); ++it){
        t = it->second - 1;  //this is for pi^(ai+1)-1
        t /= (it->first - 1);
        res *= t;
    }
    return res;
}

Upvotes: 1

Related Questions