Checks whether the given two numbers are a friendly pair-C++-php.cn

Checks whether the given two numbers are a friendly pair

WBOY

Release： 2023-08-26 23:41:20

forward

1279 people have browsed it

Checks whether the given two numbers are a friendly pair

Friendly numbers − According to number theory, a friendly number is two or more numbers with the same abundance index.

Richness Index - The richness index of a natural number can be defined as the ratio between the sum of all divisors of a natural number and the natural number itself.

The abundance of number n can be expressed as $\mathrm{\frac{\sigma(n)}{n}}$, where $\mathrm{\sigma(n)}$ represents the divisor function equal to the approximation of all n number.

For example, the abundance index of the natural number 30 is,

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

If there is a number m mn, then the number n is called a "friendly number".

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

Friendly Pair − Two numbers with the same surplus index are called "friendly pairs".

Problem Statement

Given two numbers Num1 and Num2. Returns if the two numbers are not a friendly pair.

Example 1

Input: Num1 = 30, Num2 = 140

Copy after login

Output: Yes

Copy after login

The Chinese translation of

Explanation

is:

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

Since,\frac{\sigma(30)}{30}=\frac{\sigma(140)}{140}, 30 and 140 are a pair of friendly numbers.

Example Example 2

Input: Num1 = 5, Num2 = 24

Copy after login

Output: No

Copy after login

The Chinese translation of

Explanation

is:

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

Since $\mathrm{\frac{\sigma(5)}{5}\neq\frac{\sigma(24)}{24}}$, 5 and 24 are not a friendly pair.

Method 1: Brute force method

The brute force way to solve this problem is to first find the sum of all divisors of the two numbers, then calculate the value of their abundance index, and compare to get the result.

pseudocode

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

Copy after login

Example: C implementation

In the following program, the sum of all divisors is calculated to find the abundance index.

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

Copy after login

Output

30 and 140 are friendly pair : YES

Copy after login

Time complexity - O(n), because the sumOfDivisors() function traverses a loop

Space complexity - O(1)

Method 2: Reduced form of abundance index

The simplified form of the richness index can be found by dividing both the numerator and denominator by the greatest common divisor. We then check whether the two numbers are a friendly pair by checking whether the reduced forms of richness are equal, i.e. checking whether their numerators and denominators are equal.

pseudocode

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

Copy after login

Example: C implementation

In the following program, we check whether the abundance index of the reduced form of two numbers is the same by comparing the numerator and denominator.

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

Copy after login

Output

30 and 140 are friendly pair : YES

Copy after login

Time complexity - The time complexity of the sumOfDivisors() function is O(n^1/2log2n).

Space complexity - O(1)

in conclusion

To sum up, a friendly pair refers to two natural numbers with the same abundance index, that is, the ratio of the sum of all divisors of the number to the number itself. To find whether two numbers are a friendly pair, follow the approach above, specifying a brute-force solution with time complexity O(n) and an optimized solution with time complexity O(n^1/2log2n) plan.

The above is the detailed content of Checks whether the given two numbers are a friendly pair. For more information, please follow other related articles on the PHP Chinese website!