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.