編程學習之親密數（C++描述）科技頭條網

編程學習之親密數（C++描述）

親密數

題目描述

兩個不同的自然數A和B，如果整數A的全部因子(包括1，不包括A本身)之和等於B；且整數B的全部因子(包括1，不包括B本身)之和等於A，則將整數A和B稱為親密數。求3000以內的全部親密數。

輸入

無

輸出

3000以內的全部親密數(輸出格式:(A,B)，不加換行，不加分隔符號) 一對親密數只輸出一次, 小的在前

樣例輸入

<code>無/<code>

樣例輸出

<code>(220,284)(1184,1210)(2620,2924)/<code>

分析

整道題目讀完後可發現題目關鍵是如何判斷兩個數是親密數，我們先假設存在一個函數isQMS(a,b)能幫助我們判斷兩個數是否是親密數。可以使用枚舉法。

<code>for(int a=2;a<=3000;a++)
{
    for(int b=a+1;b<=3000;b++)
    {//嵌套循環比例可能的A與B
        if(isQMS(a,b))
        {//如果是親密數，則輸出
            cout<        }
    }
}/<code>

剩下的只需判斷親密數就可以了。從定義出發，整數A的全部因子(包括1，不包括A本身)之和等於B；且整數B的全部因子(包括1，不包括B本身)之和等於A，則將整數A和B稱為親密數。判斷的關鍵在於求因子和。那麼我們假設存在一個函數sumFactor(x)能幫助我們計算x的因子和。我們可以寫出判斷親密數的函數。

<code>bool isQMS(int A,int B)
{
    int sumA=sumFactor(A);//求出a的因子和
    int sumB=sumFactor(B);//求出b的因子和
    if(sumA==B && sumB==A)
    {//判斷親密關係，返回結果
        return true;
    }else
    {
        return false;
    }
}/<code>

到這的話綜合一下整道題就可以完成了。但其實我們還能再優化一下。在主題框架的枚舉部分，進行優化，減少枚舉對象。

<code>for(int A=2;A<=3000;A++)
{
    int B=sumFactor(A);//通過計算A的因子和，直接求出對應的B.
    if(B>A && B<=3000 && A==sumFactor(B))
    {
        cout<    }
}/<code>

這樣通過求A的因子和直接計算出B,再進行相關判斷，能減少枚舉對象，使程序更有效率。

代碼實現

<code>#include <iostream>
using namespace std;

int sumFactor(int num)
{//計算num的因子和
  int sum = 0;
  for (int i = 1; i < num; i++)
   {// 遍歷1~num-1 

    if (num % i == 0)// 若i是num因子，則進行累加
      sum += i;
   }
  return sum;
}

int main()
{

  for (int A = 2; A <= 3000; A++)
   { //枚舉遍歷3000以內的數字
    int B = sumFactor(A); //B的值為A的因子和
    if (B > A && B <= 3000 && A == sumFactor(B))
     {                    //若B的因子和也為A,且在範圍內，則確定親密數
      cout << "(" << A << "," << B << ")"; //輸出親密數
     }
   }

  return 0;
}
/<iostream>/<code>