Vérifie si les deux nombres donnés forment une paire amicale

Nombres amicaux − Selon la théorie des nombres, un nombre amical est constitué de deux nombres ou plus avec le même indice d'abondance.

Indice de richesse - L'indice de richesse d'un nombre naturel peut être défini comme le rapport entre la somme de tous les diviseurs d'un nombre naturel et l'entier naturel lui-même.

L'abondance d'un nombre n peut être exprimée par $mathrm{frac{sigma(n)}{n}}$, où $mathrm{sigma(n)}$ représente la fonction diviseur égale à tous les diviseurs de n.

Par exemple, l'indice d'abondance de l'entier naturel 30 est :

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

S'il existe un nombre m mn, alors le nombre n est appelé "numéro convivial".

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

Paire amicale − Deux nombres avec le même indice excédentaire sont appelés « paires amicales ».

Énoncé du problème

Étant donné deux nombres Num1 et Num2. Renvoie si les deux nombres ne forment pas une paire amicale.

Exemple 1

Input: Num1 = 30, Num2 = 140

Output: Yes

La traduction chinoise de

Explication

est :

Explication

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

Puisque frac{sigma(30)}{30}=frac{sigma(140)}{140}, 30 et 140 sont une paire de nombres amis.

Exemple exemple 2

Input: Num1 = 5, Num2 = 24

Output: No

La traduction chinoise de

Explication

est :

Explication

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

Puisque $mathrm{frac{sigma(5)}{5}neqfrac{sigma(24)}{24}}$, 5 et 24 ne sont pas des paires amicales.

Méthode 1 : Méthode par force brute

La manière brutale de résoudre ce problème consiste d'abord à trouver la somme de tous les diviseurs des deux nombres, puis à calculer la valeur de leur indice d'abondance et à comparer pour obtenir le résultat.

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

Exemple : implémentation C++

Dans le programme ci-dessous, la somme de tous les diviseurs est calculée pour trouver l'indice d'abondance.

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

Sortie

30 and 140 are friendly pair : YES

Complexité temporelle - O(n) car la fonction sumOfDivisors() traverse une boucle

Complexité spatiale - O(1)

Méthode 2 : Forme réduite de l'indice d'abondance

La forme simplifiée de l'indice de richesse peut être trouvée en divisant le numérateur et le dénominateur par le plus grand diviseur commun. On vérifie ensuite si les deux nombres forment une paire amicale en vérifiant si les formes réduites de richesse sont égales, c'est-à-dire en vérifiant si leurs numérateurs et dénominateurs sont égaux.

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

Exemple : implémentation C++

Dans le programme ci-dessous, nous vérifions si l'indice d'abondance de la forme réduite de deux nombres est le même en comparant le numérateur et le dénominateur.

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

Sortie

30 and 140 are friendly pair : YES

Complexité temporelle - La complexité temporelle de la fonction sumOfDivisors() est O(n^1/2log2n).

Complexité spatiale - O(1)

Conclusion

Pour résumer, une paire amicale fait référence à deux nombres naturels ayant le même indice d'abondance, c'est-à-dire le rapport de la somme de tous les diviseurs du nombre au nombre lui-même. Pour savoir si deux nombres forment une paire amicale, suivez l'approche ci-dessus, en spécifiant une solution par force brute avec une complexité temporelle O(n) et une solution optimisée avec une complexité temporelle O(n^1/2log2n).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!