搜尋
首頁後端開發C++檢查給定的兩個數字是否是友善數對

檢查給定的兩個數字是否是友善數對

友善數 − 根據數論,友善數是指兩個或更多具有相同豐度指數的數。

豐富度指數 - 自然數的豐富度指數可以定義為自然數的所有除數總和與自然數本身之間的比率。

數字n的豐度可以表示為$\mathrm{\frac{\sigma(n)}{n}}$,其中$\mathrm{\sigma(n)}$表示除數函數等於所有n 的約數。

例如,自然數30的豐度指數為,

$$\mathrm{\frac{\sigma(30)}{30}=\frac{1 2 3 5 6 10 15 30}{30}=\frac{72}{ 30}=\frac{12 }{5}}$$

#如果存在一個數m mn,則數n稱為「友善數」。

$\mathrm{\frac{\sigma(m)}{m}=\frac{\sigma(n)}{n}}$

友善對 − 具有相同盈餘指數的兩個數字被稱為「友善對」。

問題陳述

給定兩個數字 Num1 和 Num2。如果這兩個數字不是友好的一對,則返回。

範例 1

Input: Num1 = 30, Num2 = 140
Output: Yes

Explanation

的中文翻譯為:

解釋

$$\mathrm{\frac{\sigma(30)}{30}=\frac{1 2 3 5 6 10 15 30}{30}=\frac{72}{ 30}=\frac{12 }{5}}$$

#$$\mathrm{\frac{\sigma(140)}{140}=\frac{1 2 4 5 7 10 14 20 28 35 70 140}{140 }=\frac{336}{140}= \frac{12}{5}}$$

#由於,\frac{\sigma(30)}{30}=\frac{\sigma(140)}{140},因此30和140是一對友善數。

範例範例2

Input: Num1 = 5, Num2 = 24
Output: No

Explanation

的中文翻譯為:

解釋

$$\mathrm{\frac{\sigma(5)}{5}=\frac{1 5}{5}=\frac{6}{5}=\frac{6}{5}} $ $

$$\mathrm{\frac{\sigma(24)}{24}=\frac{1 2 3 4 6 8 12 24}{24}=\frac{60}{ 24}=\frac{15 }{6}}$$

由於$\mathrm{\frac{\sigma(5)}{5}\neq\frac{\sigma(24)}{24}}$,因此5和24不是友善的對。 p>

方法一:蠻力方法

解決這個問題的蠻力方法是先找到兩個數字的所有約數的和,然後計算它們的豐度指數的值,並進行比較以獲得結果。

虛擬程式碼

procedure sumOfDivisors (n)
   sum = 0
   for i = 1 to n
      if i is a factor of n
         sum = sum + i
      end if
   ans = sum
end procedure

procedure friendlyPair (num1, num2)
   sum1 = sumOfDivisors (num1)
   sum2 = sumOfDivisors (num2)
   abIndex1 = sum1 / num1
   abIndex2 = sum2 / num2
   if (abIndex1 == abIndex2)
      ans = TRUE
   else
      ans = FALSE
   end if
end procedure

範例:C 實作

在下面的程式中,計算所有除數的總和以找到豐度指數。

#include <bits/stdc++.h>
using namespace std;

// Function to find sum of all the divisors of number n
int sumOfDivisors(int n){
   int sum = 0;
   for (int i = 1; i <= n; i++){
      if (n % i == 0){
         sum += i;
      }
   }
   return sum;
}
// Function to find if two numbers are friendly pairs or not
int friendlyPair(int num1, int num2){

   // Finding the sum of all divisors of num1 and num2
   int sum1 = sumOfDivisors(num1);
   int sum2 = sumOfDivisors(num2);
   
   // Calculating the abundancy index as the ratio of the sum of divisors by the number
   int abIn1 = sum1 / num1, abIn2 = sum2 / num2;
   
   // Friendly pair if the abundancy index of both the numbers are same
   if (abIn1 == abIn2){
      return true;
   }
   return false;
}
int main(){
   int num1 = 30, num2 = 140;
   cout << num1 << " and " << num2 << " are friendly pair : ";
   if (friendlyPair(num1, num2)){
      cout << "YES";
   }
   else{
      cout << "NO";
   }
   return 0;
} 

輸出

30 and 140 are friendly pair : YES

時間複雜度 - O(n),因為 sumOfDivisors() 函數遍歷一個迴圈

空間複雜度 - O(1)

方法 2:簡化形式的豐度指數

將分子和分母都除以最大公約數,可以找到豐富度指數的簡化形式。然後,透過檢查豐富度的簡化形式是否相等來檢查這兩個數是否為友善數對,即檢查它們的分子和分母是否相等。

虛擬程式碼

procedure sumOfDivisors (n)
   ans = 1
   for i = 1 to sqrt(n)
      count = 0
      sum = 1
      term = 1
      while n % i == 0
         count = count + 1
         n = n / i
         term = term * i
         sum = sum + term
      ans = ans * sum
   if n >= 2
      ans = ans * (n + 1)
   end if
end procedure

procedure gcd (n1, n2)
   if n1 == 0
      return n2
   end if
   rem = n2 % n1
   return gcd (rem, n2)
end procedure

procedure friendlyPair (num1, num2)
   sum1 = sumOfDivisors (num1)
   sum2 = sumOfDivisors (num2)
   gcd1 = gcd (num1, sum1)
   gcd2 = gcd (num2, sum2)
   if (num1 / gcd1 == num2 / gcd2) && (sum1 / gcd1 == sum2 / gcd2)
      ans = TRUE
   else
      ans = FALSE
   end if
end procedure

範例:C 實作

在下面的程序中,我們透過比較分子和分母來檢查兩個數字的簡化形式的豐度指數是否相同。

#include <bits/stdc++.h>
using namespace std;

// Function to find the sum of all the divisors of number n
int sumOfDivisors(int n){
   int ans = 1;
   
   // By looping till sqrt(n), we traverse all the prime factors of n
   for (int i = 2; i <= sqrt(n); i++){
      int cnt = 0, sum = 1, term = 1;
      while (n % i == 0){
         cnt++;
         
         // Reducing the value of n
         n /= i;
         term *= i;
         sum += term;
      }
      ans *= sum;
   }
   
   // When n is a prime number greater than 2
   if (n >= 2){
      ans *= (n + 1);
   }
   return ans;
}

// Function to find the gcd of two numbers
int gcd(int num1, int num2){
   if (num1 == 0) {
      return num2;
   }
   int rem = num2 % num1;
   return gcd(rem, num1);
}

// Function to find if two numbers are friendly pairs or not
int friendlyPair(int num1, int num2){

   // Finding the sum of all divisors of num1 and num2
   int sum1 = sumOfDivisors(num1);
   int sum2 = sumOfDivisors(num2);
   
   // Finding gcd of num and the sum of its divisors
   int gcd1 = gcd(num1, sum1);
   int gcd2 = gcd(num2, sum2);
   
   // Checking if the numerator and denominator of the reduced abundancy index are the same or not
   if (((num1 / gcd1) == (num2 / gcd2)) && ((sum1 / gcd1) == (sum2 / gcd2))){
      return true;
   }
   return false;
}
int main(){
   int num1 = 30, num2 = 140;
   cout << num1 << " and " << num2 << " are friendly pair : ";
   if (friendlyPair(num1, num2)){
      cout << "YES";
   }
   else{
      cout << "NO";
   }
   return 0;
}

輸出

30 and 140 are friendly pair : YES

時間複雜度 - sumOfDivisors() 函數的時間複雜度為 O(n1/2log2n)。

空間複雜度 - O(1)

結論

綜上所述,友善對是指豐度指數相同的兩個自然數,即該數的所有約數總和與該數本身的比值。若要找出兩個數字是否為友善對,請遵循上述方法,指定時間複雜度為O(n) 的強力解和時間複雜度為O(n1/2log2n) 的最佳化解決方案。

以上是檢查給定的兩個數字是否是友善數對的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文轉載於:tutorialspoint。如有侵權,請聯絡admin@php.cn刪除
c#vs. c:每種語言都擅長c#vs. c:每種語言都擅長Apr 12, 2025 am 12:08 AM

C#適合需要高開發效率和跨平台支持的項目,而C 適用於需要高性能和底層控制的應用。 1)C#簡化開發,提供垃圾回收和豐富類庫,適合企業級應用。 2)C 允許直接內存操作,適用於遊戲開發和高性能計算。

繼續使用C:耐力的原因繼續使用C:耐力的原因Apr 11, 2025 am 12:02 AM

C 持續使用的理由包括其高性能、廣泛應用和不斷演進的特性。 1)高效性能:通過直接操作內存和硬件,C 在系統編程和高性能計算中表現出色。 2)廣泛應用:在遊戲開發、嵌入式系統等領域大放異彩。 3)不斷演進:自1983年發布以來,C 持續增加新特性,保持其競爭力。

C和XML的未來:新興趨勢和技術C和XML的未來:新興趨勢和技術Apr 10, 2025 am 09:28 AM

C 和XML的未來發展趨勢分別為:1)C 將通過C 20和C 23標準引入模塊、概念和協程等新特性,提升編程效率和安全性;2)XML將繼續在數據交換和配置文件中佔據重要地位,但會面臨JSON和YAML的挑戰,並朝著更簡潔和易解析的方向發展,如XMLSchema1.1和XPath3.1的改進。

現代C設計模式:構建可擴展和可維護的軟件現代C設計模式:構建可擴展和可維護的軟件Apr 09, 2025 am 12:06 AM

現代C 設計模式利用C 11及以後的新特性實現,幫助構建更靈活、高效的軟件。 1)使用lambda表達式和std::function簡化觀察者模式。 2)通過移動語義和完美轉發優化性能。 3)智能指針確保類型安全和資源管理。

C多線程和並發:掌握並行編程C多線程和並發:掌握並行編程Apr 08, 2025 am 12:10 AM

C 多線程和並發編程的核心概念包括線程的創建與管理、同步與互斥、條件變量、線程池、異步編程、常見錯誤與調試技巧以及性能優化與最佳實踐。 1)創建線程使用std::thread類,示例展示瞭如何創建並等待線程完成。 2)同步與互斥使用std::mutex和std::lock_guard保護共享資源,避免數據競爭。 3)條件變量通過std::condition_variable實現線程間的通信和同步。 4)線程池示例展示瞭如何使用ThreadPool類並行處理任務,提高效率。 5)異步編程使用std::as

C深度潛水:掌握記憶管理,指針和模板C深度潛水:掌握記憶管理,指針和模板Apr 07, 2025 am 12:11 AM

C 的內存管理、指針和模板是核心特性。 1.內存管理通過new和delete手動分配和釋放內存,需注意堆和棧的區別。 2.指針允許直接操作內存地址,使用需謹慎,智能指針可簡化管理。 3.模板實現泛型編程,提高代碼重用性和靈活性,需理解類型推導和特化。

C和系統編程:低級控制和硬件交互C和系統編程:低級控制和硬件交互Apr 06, 2025 am 12:06 AM

C 適合系統編程和硬件交互,因為它提供了接近硬件的控制能力和麵向對象編程的強大特性。 1)C 通過指針、內存管理和位操作等低級特性,實現高效的系統級操作。 2)硬件交互通過設備驅動程序實現,C 可以編寫這些驅動程序,處理與硬件設備的通信。

使用C的遊戲開發:構建高性能遊戲和模擬使用C的遊戲開發:構建高性能遊戲和模擬Apr 05, 2025 am 12:11 AM

C 適合構建高性能遊戲和仿真係統,因為它提供接近硬件的控制和高效性能。 1)內存管理:手動控制減少碎片,提高性能。 2)編譯時優化:內聯函數和循環展開提昇運行速度。 3)低級操作:直接訪問硬件,優化圖形和物理計算。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
3 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能