Dados dos enteros positivos N , M . La tarea es verificar si N y M son pares amigos o no.
En teoría de números, los pares amistosos son dos números con un índice de abundancia común, la relación entre la suma de los divisores de un número y el número mismo, es decir, ?(n)/n. Entonces, dos números n y m son números amistosos si
?(n)/n = ?(m)/m.
donde ?(n) es la suma de los divisores de n.
Ejemplos:
Input : n = 6, m = 28 Output : Yes Explanation: Divisor of 6 are 1, 2, 3, 6. Divisor of 28 are 1, 2, 4, 7, 14, 28. Sum of divisor of 6 and 28 are 12 and 56 respectively. Abundancy index of 6 and 28 are 2. So they are friendly pair. Input : n = 18, m = 26 Output : No
La idea es encontrar la suma del divisor de n y m. Y para comprobar si el índice de abundancia de n y m, encontraremos el Máximo Común Divisor de n y m con su suma de divisores. Y compruebe si la forma reducida del índice de abundancia de n y m son iguales comprobando si su numerador y denominador son iguales o no. Para encontrar la forma reducida, dividiremos numerador y denominador por MCD.
A continuación se muestra la implementación de la idea anterior:
C++
// Check if the given two number // are friendly pair or not. #include <bits/stdc++.h> using namespace std; // Returns sum of all factors of n. int sumofFactors(int n) { // Traversing through all prime factors. int res = 1; for (int i = 2; i <= sqrt(n); i++) { int count = 0, curr_sum = 1; int curr_term = 1; while (n % i == 0) { count++; // THE BELOW STATEMENT MAKES // IT BETTER THAN ABOVE METHOD // AS WE REDUCE VALUE OF n. n = n / i; curr_term *= i; curr_sum += curr_term; } res *= curr_sum; } // This condition is to handle // the case when n is a prime // number greater than 2. if (n >= 2) res *= (1 + n); return res; } // Function to return gcd of a and b int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to check if the given two // number are friendly pair or not. bool checkFriendly(int n, int m) { // Finding the sum of factors of n and m int sumFactors_n = sumofFactors(n); int sumFactors_m = sumofFactors(m); // finding gcd of n and sum of its factors. int gcd_n = gcd(n, sumFactors_n); // finding gcd of m and sum of its factors. int gcd_m = gcd(m, sumFactors_m); // checking is numerator and denominator of // abundancy index of both number are equal // or not. if (n / gcd_n == m / gcd_m && sumFactors_n / gcd_n == sumFactors_m / gcd_m) return true; else return false; } // Driver code int main() { int n = 6, m = 28; checkFriendly(n, m) ? (cout << "Yes\n") : (cout << "No\n"); return 0; }
Java
// Java code to check if the given two number // are friendly pair or not. class GFG { // Returns sum of all factors of n. static int sumofFactors(int n) { // Traversing through all prime factors. int res = 1; for (int i = 2; i <= Math.sqrt(n); i++) { int count = 0, curr_sum = 1; int curr_term = 1; while (n % i == 0) { count++; // THE BELOW STATEMENT MAKES // IT BETTER THAN ABOVE METHOD // AS WE REDUCE VALUE OF n. n = n / i; curr_term *= i; curr_sum += curr_term; } res *= curr_sum; } // This condition is to handle // the case when n is a prime // number greater than 2. if (n >= 2) res *= (1 + n); return res; } // Function to return gcd of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to check if the given two // number are friendly pair or not. static boolean checkFriendly(int n, int m) { // Finding the sum of factors of n and m int sumFactors_n = sumofFactors(n); int sumFactors_m = sumofFactors(m); // finding gcd of n and sum of its factors. int gcd_n = gcd(n, sumFactors_n); // finding gcd of m and sum of its factors. int gcd_m = gcd(m, sumFactors_m); // checking is numerator and denominator of // abundancy index of both number are equal // or not. if (n / gcd_n == m / gcd_m && sumFactors_n / gcd_n == sumFactors_m / gcd_m) return true; else return false; } //driver code public static void main (String[] args) { int n = 6, m = 28; if(checkFriendly(n, m)) System.out.print("Yes\n"); else System.out.print("No\n"); } } // This code is contributed by Anant Agarwal.
Python3
# Check if the given two number # are friendly pair or not. import math # Returns sum of all factors of n. def sumofFactors(n): # Traversing through all prime factors. res = 1 for i in range(2, int(math.sqrt(n)) + 1): count = 0; curr_sum = 1; curr_term = 1 while (n % i == 0): count += 1 # THE BELOW STATEMENT MAKES # IT BETTER THAN ABOVE METHOD # AS WE REDUCE VALUE OF n. n = n // i curr_term *= i curr_sum += curr_term res *= curr_sum # This condition is to handle # the case when n is a prime # number greater than 2. if (n >= 2): res *= (1 + n) return res # Function to return gcd of a and b def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Function to check if the given two # number are friendly pair or not. def checkFriendly(n, m): # Finding the sum of factors of n and m sumFactors_n = sumofFactors(n) sumFactors_m = sumofFactors(m) # Finding gcd of n and sum of its factors. gcd_n = gcd(n, sumFactors_n) # Finding gcd of m and sum of its factors. gcd_m = gcd(m, sumFactors_m) # checking is numerator and denominator # of abundancy index of both number are # equal or not. if (n // gcd_n == m // gcd_m and sumFactors_n // gcd_n == sumFactors_m // gcd_m): return True else: return False # Driver code n = 6; m = 28 if(checkFriendly(n, m)): print("Yes") else: print("No") # This code is contributed by Anant Agarwal.
C#
// C# code to check if the // given two number are // friendly pair or not using System; class GFG { // Returns sum of all //factors of n. static int sumofFactors(int n) { // Traversing through all // prime factors. int res = 1; for (int i = 2; i <= Math.Sqrt(n); i++) { int count = 0, curr_sum = 1; int curr_term = 1; while (n % i == 0) { count++; // THE BELOW STATEMENT MAKES // IT BETTER THAN ABOVE METHOD // AS WE REDUCE VALUE OF n. n = n / i; curr_term *= i; curr_sum += curr_term; } res *= curr_sum; } // This condition is to handle // the case when n is a prime // number greater than 2. if (n >= 2) res *= (1 + n); return res; } // Function to return gcd // of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to check if the // given two number are // friendly pair or not static bool checkFriendly(int n, int m) { // Finding the sum of factors // of n and m int sumFactors_n = sumofFactors(n); int sumFactors_m = sumofFactors(m); // finding gcd of n and // sum of its factors. int gcd_n = gcd(n, sumFactors_n); // finding gcd of m and sum // of its factors. int gcd_m = gcd(m, sumFactors_m); // checking is numerator and // denominator of abundancy // index of both number are // equal or not if (n / gcd_n == m / gcd_m && sumFactors_n / gcd_n == sumFactors_m / gcd_m) return true; else return false; } // Driver code public static void Main (String[] args) { int n = 6, m = 28; if(checkFriendly(n, m)) Console.Write("Yes\n"); else Console.Write("No\n"); } } // This code is contributed by parshar...
PHP
<?php // PHP program to check if the given // two number are friendly pair or not. // Returns sum of all factors of n. function sumofFactors( $n) { // Traversing through all // prime factors. $res = 1; for ($i = 2; $i <= sqrt($n); $i++) { $count = 0; $curr_sum = 1; $curr_term = 1; while ($n % $i == 0) { $count++; // THE BELOW STATEMENT MAKES // IT BETTER THAN ABOVE METHOD // AS WE REDUCE VALUE OF n. $n = $n / $i; $curr_term *= $i; $curr_sum += $curr_term; } $res *= $curr_sum; } // This condition is to handle // the case when n is a prime // number greater than 2. if ($n >= 2) $res *= (1 + $n); return $res; } // Function to return // gcd of a and b function gcd($a, $b) { if ($a == 0) return $b; return gcd($b % $a, $a); } // Function to check if the given two // number are friendly pair or not. function checkFriendly($n, $m) { // Finding the sum of // factors of n and m $sumFactors_n = sumofFactors($n); $sumFactors_m = sumofFactors($m); // finding gcd of n and // sum of its factors. $gcd_n = gcd($n, $sumFactors_n); // finding gcd of m and // sum of its factors. $gcd_m = gcd($m, $sumFactors_m); // checking is numerator // and denominator of // abundancy index of // both number are equal // or not. if ($n / $gcd_n == $m / $gcd_m and $sumFactors_n / $gcd_n == $sumFactors_m / $gcd_m) return true; else return false; } // Driver code $n = 6; $m = 28; if(checkFriendly($n, $m)) echo "Yes" ; else echo "No"; // This code is contributed by anuj_67. ?>
Javascript
<script> // JavaScript program to check if the given two number // are friendly pair or not. // Returns sum of all factors of n. function sumofFactors(n) { // Traversing through all prime factors. let res = 1; for (let i = 2; i <= Math.sqrt(n); i++) { let count = 0, curr_sum = 1; let curr_term = 1; while (n % i == 0) { count++; // THE BELOW STATEMENT MAKES // IT BETTER THAN ABOVE METHOD // AS WE REDUCE VALUE OF n. n = n / i; curr_term *= i; curr_sum += curr_term; } res *= curr_sum; } // This condition is to handle // the case when n is a prime // number greater than 2. if (n >= 2) res *= (1 + n); return res; } // Function to return gcd of a and b function gcd(a, b) { if (a == 0) return b; return gcd(b % a, a); } // Function to check if the given two // number are friendly pair or not. function checkFriendly(n, m) { // Finding the sum of factors of n and m let sumFactors_n = sumofFactors(n); let sumFactors_m = sumofFactors(m); // finding gcd of n and sum of its factors. let gcd_n = gcd(n, sumFactors_n); // finding gcd of m and sum of its factors. let gcd_m = gcd(m, sumFactors_m); // checking is numerator and denominator of // abundancy index of both number are equal // or not. if (n / gcd_n == m / gcd_m && sumFactors_n / gcd_n == sumFactors_m / gcd_m) return true; else return false; } // Driver Code let n = 6, m = 28; if(checkFriendly(n, m)) document.write("Yes\n"); else document.write("No\n"); // This code is contributed by avijitmondal1998. </script>
Producción
Yes
Complejidad de Tiempo: O(√n log n)
Espacio Auxiliar: O(1)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.