# Determine amicable pairs within confines of Θ(n)

I had to implement a program that takes a number userNum from the user and finds all perfect numbers and pairs of amicable numbers within the range $\lbrace 2, \ldots, \texttt{userNum} \rbrace$ and output them to the user.

Requirements

1. Implement function void AnalyzeDivisors(int num, int& outCountDivs, int& outSumDivs)
2. implement bool IsPerfect(int num) using AnalyzeDivisors
3. Use functions to write a program that reads from the user a positive integer and prints all perfect numbers between 2 and M and All pairs of amicable numbers that are between 2 and M (both numbers must be in range).
4. Calls to AnalyzeDivisors must be kept to $\Theta(m)$ times all together.

I have not been able to satisfy requirement 4 … Currently my algorithm is very inefficient and I'm unsure how to do it otherwise. Any recommendations on how to remain within $\Theta(m)$ in reference to AnalyzeDivisors would be greatly appreciated.

Code below:

main:

const string IS_PERFECT_NUM = " is a perfect number.";

void AnalyzeDividors(int num, int& outCountDivs, int& outSumDivs);
bool IsPerfect(int userNum, int outSumDivs);

int main()
{
int userNum;

//Request number input from the user
cout << "Please input a positive integer num (>= 2): " << endl;
cin >> userNum;

for (int counter = 2; counter <= userNum; counter++)
{
//Set variables
int outCountDivs = 0, outSumDivs = 0;
bool perfectNum = false, isAmicablePair = false;

//Analyze dividors
AnalyzeDividors(counter, outCountDivs, outSumDivs);

//determine perfect num
perfectNum = IsPerfect(counter, outSumDivs);

if (perfectNum)
cout << endl << counter << IS_PERFECT_NUM;

//Smallest pair of amicable numbers (220,284)...No need to check if not above range
if (userNum >= 284)
{

for (int amicablePairCounter = counter + 1; amicablePairCounter <= userNum; amicablePairCounter++)
{
//Determine if amicable pairs exist by checking against outCountDivs and outSumDivs from prior counter number
int otherAmicablePairSum = 0, otherOutCountDivs = 0;

AnalyzeDividors(amicablePairCounter, otherOutCountDivs, otherAmicablePairSum);

if (otherAmicablePairSum == counter && outSumDivs == amicablePairCounter)
cout << endl << amicablePairCounter << " and " << counter << " are an amicable pair.";
}
}

}

return 0;
}


Analyze Dividors

void AnalyzeDividors(int num, int& outCountDivs, int& outSumDivs)
{
int divisorCounter;

for (divisorCounter = 1; divisorCounter <= sqrt(num); divisorCounter++)
{
if (num % divisorCounter == 0 && num / divisorCounter != divisorCounter && num / divisorCounter != num)
{
//both counter and num/divisorCounter
outSumDivs += divisorCounter + (num / divisorCounter);
outCountDivs += 2;
}

else if ((num % divisorCounter == 0 && num / divisorCounter == divisorCounter) || num/divisorCounter == num)
{
//Just divisorCounter
outSumDivs += divisorCounter;
outCountDivs += 1;
}
}
}


IsPerfect

bool IsPerfect(int userNum, int outSumDivs)
{

if (userNum == outSumDivs)
return true;
else
return false;

}

• You can memoize the results of AnalyzeDivisors, but you'll have to do it outside the method itself to decrease the number of calls. – David Harkness Feb 27 '17 at 4:36