mardi 11 mai 2021

Speed problem for summation (sum of divisors)

I should implement this summation in C ++. I have tried with this code, but with very high numbers up to 10 ^ 12 it takes too long.

This is the summation. For any positive integer k, let d(k) denote the number of positive divisors of k (including 1 and k itself). For example, for the number 4: 1 has 1 divisor, 2 has two divisors, 3 has two divisors, and 4 has three divisors. So the result would be 8.

This is my code:

#include <iostream>
#include <algorithm>

using namespace std;

int findDivisors(long long n) 
{
    int c=0;
    for(int j=1;j*j<=n;j++)
    {
        if(n%j==0)
        {
            c++;
            if(j!=(n/j))
            {
                c++;
            }
        }
    }
    return c;
}

long long compute(long long n)
{
    long long sum=0;
    for(int i=1; i<=n; i++)
    {
        sum += (findDivisors(i));
    }
    return sum;
}

int main()
{
    int n, divisors;

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> n;

    cout << compute(n);
}

I think it's not just a simple optimization problem, but maybe I should change the algorithm entirely. Would anyone have any ideas to speed it up? Thank you.

Aucun commentaire:

Enregistrer un commentaire