ExOfDe ExOfDe - 22 days ago 8
C++ Question

Amicable Numbers: Runtime is to long. What could cause that? algorithm complexity?

I've got a little runtime problem with my code. The code works fine except it takes dozens of minutes on Windows and hours on Linux to run.

class AmicableNumbersBeta
{
private:
long start;
long end;
std::vector<long> numbers;

protected:

long getStart() { return start;}
long getEnd() { return end;}

void setStart(long start) { this->start = start;}
void setEnd(long end) { this->end=end;}

long SumOfDivisors(long value)
{
long result = 0;
long half_value = value / 2;

for (long i = 1; i <= half_value; i++)
{

if (value % i == 0)
{
result += i;
}
}

return result;
}

void AddNumber(long value)
{
this->numbers.push_back(value);
}

public:

AmicableNumbersBeta(long Start, long End) : start(Start),end(End){}


void Calculate()
{
// clear old calculation, if any
this->numbers.clear();


for (long i = getStart(); i < getEnd(); i++)
{

long s1 = SumOfDivisors(i);
long s2 = SumOfDivisors(s1);

if (s2 == i && i < s1)
{
std::cout<<"-- adding ( "<<i<<" )\n";
this->AddNumber(i);
}
}
}

};


if i try to run this programm now and it starts to calculate Alpha til 1000000 numbers a checked it takes hours literally. But according to my teacher it should take only a few seconds to calculate.

int main() {
std::cout << "Hello, World!" << std::endl;

AmicableNumbersBeta Alpha(1,1000000);
AmicableNumbersBeta Beta( 1,100000);
AmicableNumbersBeta Gamma(1,10000);
AmicableNumbersBeta Delta(1,1000);

std::cout<<"Delta\n";
Delta.Calculate();

std::cout<<"\nGamma\n";
Gamma.Calculate();

std::cout<<"\nBeta\n";
Beta.Calculate();

std::cout<<"\nAlpha\n";
Alpha.Calculate();

std::cout << "Bye, World!" << std::endl;
return 0;
}


I honestly do not understand what could cause this huge "delay".

The platforms i use are Linux Debian with GCC 4.9
and Windows VS 15

I really would appreciate if someone could point out the reason for this behaviour .

Answer

As mentioned in the comments, your code can be optimized in many ways, by using memoization or sieves or even parallelism.

While in real applications, I may go for such optimizations, you don't need such "complex" things here - You only need a single improvement to make your code run in a few seconds instead of minutes: You need to compute divisors only up to the square root of your value. So basically:

long SumOfDivisors(long value)
{
    long result = 1; 

    for (long i = 2; i * i <= value; i++)
    {
       if (value % i == 0)
       {
           result += i;
           if (value / i != i) {
               result += value / i;
           }
       }
    }

    return result;
}

With this simple modification, you can compute Amicable numbers up to 1000000 in a few seconds.