在 Theta(n) 的范围内确定友好配对

Question

我正在尝试实现一个程序，该程序从用户那里读取一个正整数并输出 2 到 userNum 之间的所有完美数字。它还输出所有介于 2 和 userNum 之间的友好数对。两个数字都必须在范围内。我正在为此苦苦挣扎。

要求： 1) 对 AnalyzeDivisors 的调用必须一起保持到 theta(userNum) 次。 2) 函数 void AnalyzeDivisors 必须采用以下参数 int num, int& outCountDivs, int& outSumDivs。 3) 函数 bool IsPerfect 必须接受以下参数 int num.

老实说，我不知道如何在那个效率范围内做到这一点。我目前能够通过将规则弯曲到 IsPerfect 函数的参数来确定范围内的所有完美数字，但是我如何在不调用 Analyze Dividors 的情况下确定友好的对？

如有任何帮助，我们将不胜感激！代码如下：

主要

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, otherAmicablePair = 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;

    }

    return 0;
}

分析除数

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;
        }
    }
}

完美

bool IsPerfect(int userNum, int outSumDivs)
{

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

}

Answer 1

我想我找到了符合要求的解决方案。我通过将每个数字和除数之和存储在地图中来找到友好数字。如果在map中输入一个数的除数和，并且除数的和是当前数，那么他们是友好的。

因为每次都会保存结果，所以每个号码只调用一次AnalyzeDivisors。

请原谅懒惰的变量命名。

#include <iostream>
#include <map>
#include <cmath>

void AnalyzeDivisors(int num, int& divc, int &divs)
{
    divc = 1;
    divs = 1;
    for (int x = 2, y = std::sqrt(num); x <= y; ++x)
    {
        if (num % x == 0)
        {
            ++divc;
            divs += x;
            if (num / x != x)
            {
                ++divc;
                divs += num / x;
            }
        }
    }
}

bool IsPerfect(int num)
{
    static std::map<int, int> amicable;
    int divc = 0, divs = 0;
    AnalyzeDivisors(num, divc, divs);
    if (amicable.find(divs) != amicable.end() && amicable[divs] == num)
        std::cout << num << " and " << divs << " are best bros for life.\n";
    amicable[num] = divs;
    return num == divs;
}

int main()
{
    int num;
    std::cout << "Pick a number: ";
    std::cin >> num;
    for (int x = 2; x < num; ++x)
    {
        if (IsPerfect(x))
            std::cout << x << " is perfect in every way!\n";
    }
}

在 Theta(n) 的范围内确定友好配对

Determine Amicable Pairs within Confines of Theta(n)

c++

performance

coding-efficiency