Überprüft, ob die angegebenen zwei Zahlen ein freundliches Paar sind

Freundliche Zahlen − Nach der Zahlentheorie besteht eine freundliche Zahl aus zwei oder mehr Zahlen mit demselben Häufigkeitsindex.

Reichtumsindex – Der Reichtumsindex einer natürlichen Zahl kann als das Verhältnis zwischen der Summe aller Teiler einer natürlichen Zahl und der natürlichen Zahl selbst definiert werden.

Die Häufigkeit einer Zahl n kann als $mathrm{frac{sigma(n)}{n}}$ ausgedrückt werden, wobei $mathrm{sigma(n)}$ die Teilerfunktion darstellt, die allen Teilern von n entspricht.

Zum Beispiel ist der Häufigkeitsindex der natürlichen Zahl 30

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

Wenn es eine Zahl m mn gibt, dann wird die Zahl n als „freundliche Zahl“ bezeichnet.

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

Friendly Pair − Zwei Zahlen mit demselben Überschussindex werden „Friendly Pairs“ genannt.

Problemstellung

Gegeben sind zwei Zahlen Num1 und Num2. Gibt zurück, wenn die beiden Zahlen kein freundliches Paar sind.

Beispiel 1

Input: Num1 = 30, Num2 = 140

Output: Yes

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

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

Da frac{sigma(30)}{30}=frac{sigma(140)}{140}, sind 30 und 140 ein Paar freundlicher Zahlen.

Beispiel Beispiel 2

Input: Num1 = 5, Num2 = 24

Output: No

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

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

Da $mathrm{frac{sigma(5)}{5}neqfrac{sigma(24)}{24}}$ sind 5 und 24 keine befreundeten Paare.

Methode 1: Brute-Force-Methode

Die Brute-Force-Methode zur Lösung dieses Problems besteht darin, zunächst die Summe aller Teiler der beiden Zahlen zu ermitteln, dann den Wert ihres Häufigkeitsindex zu berechnen und zu vergleichen, um das Ergebnis zu erhalten.

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

Beispiel: C++-Implementierung

Im Programm unten wird die Summe aller Teiler berechnet, um den Häufigkeitsindex zu ermitteln.

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

Ausgabe

30 and 140 are friendly pair : YES

Zeitliche Komplexität – O(n), da die Funktion sumOfDivisors() eine Schleife durchläuft

Raumkomplexität – O(1)

Methode 2: Reduzierte Form des Abundanzindex

Die vereinfachte Form des Reichtumsindex kann gefunden werden, indem sowohl der Zähler als auch der Nenner durch den größten gemeinsamen Teiler dividiert werden. Anschließend prüfen wir, ob die beiden Zahlen ein freundliches Paar sind, indem wir prüfen, ob die reduzierten Formen des Reichtums gleich sind, d. h. prüfen, ob ihre Zähler und Nenner gleich sind.

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

Beispiel: C++-Implementierung

Im folgenden Programm prüfen wir, ob der Häufigkeitsindex der reduzierten Form zweier Zahlen gleich ist, indem wir Zähler und Nenner vergleichen.

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

Ausgabe

30 and 140 are friendly pair : YES

Zeitkomplexität – Die Zeitkomplexität der Funktion sumOfDivisors() beträgt O(n^1/2log2n).

Raumkomplexität – O(1)

Fazit

Zusammenfassend lässt sich sagen, dass sich ein freundliches Paar auf zwei natürliche Zahlen mit demselben Häufigkeitsindex bezieht, d. h. dem Verhältnis der Summe aller Teiler der Zahl zur Zahl selbst. Um herauszufinden, ob zwei Zahlen ein freundliches Paar sind, befolgen Sie den oben genannten Ansatz und geben Sie eine Brute-Force-Lösung mit der Zeitkomplexität O(n) und eine optimierte Lösung mit der Zeitkomplexität O(n^1/2log2n) an.

Das obige ist der detaillierte Inhalt vonÜberprüft, ob die angegebenen zwei Zahlen ein freundliches Paar sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!