1
\$\begingroup\$

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;

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.