ExOfDe - 1 year ago 62
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;
}

{
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)
{
}
}
}

};
``````

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 .

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download