Los números prometidos son dos números positivos tales que la suma de los divisores propios de cada número es uno más que (o uno más) el valor del otro número. Nuestra tarea es encontrar estos pares de manera eficiente.
Ejemplo :
(48, 75) is an example of Betrothed numbers
Divisors of 48 : 1, 2, 3, 4, 6, 8, 12,
16, 24. Their sum is 76.
Divisors of 75 : 1, 3, 5, 15, 25. Their
sum is 49.
Dado un entero positivo n, imprima todos los números Brothered (que es un par) de modo que uno de los números de cada par sea menor que n.
Ejemplo :
Input : n = 1000
Output : (48, 75), (140, 195)
Input : n = 10000
Output : (48, 75), (140, 195), (1050, 1925)
(1575, 1648), (2024, 2295), (5775,
6128) (8892, 16587), (9504, 20735)
La idea utilizada en el siguiente programa es simple. Recorremos todos los números del 1 al n-1. Para cada número num1, encontramos la suma de sus divisores propios , digamos sum1. Después de encontrar sum1, verificamos si el número num2 = sum1 + 1 que tiene una suma de divisores como num1 + 1
C++
// CPP program to find Betrothed number pairs
// such that one of the numbers is smaller than
// a given number n.
#include <iostream>
using namespace std;
void BetrothedNumbers(int n)
{
for (int num1 = 1; num1 < n; num1++) {
// Calculate sum of num1's divisors
int sum1 = 1; // 1 is always a divisor
// i=2 because we don't want to include
// 1 as a divisor.
for (int i = 2; i * i <= num1; i++)
{
if (num1 % i == 0) {
sum1 += i;
// we do not want to include
// a divisor twice
if (i * i != num1)
sum1 += num1 / i;
}
}
// Now check if num2 is the sum of
// divisors of num1, so only the num
// that equals to sum of divisors of
// num1 is a nominee for num1.
/* This if is for not to make a
duplication of the nums, because
if sum1 is smaller than num1, this
means that we have already checked
the smaller one.*/
if (sum1 > num1)
{
int num2 = sum1 - 1;
int sum2 = 1;
for (int j = 2; j * j <= num2; j++)
{
if (num2 % j == 0) {
sum2 += j;
if (j * j != num2)
sum2 += num2 / j;
}
}
// checks if the sum divisors of
// num2 is equal to num1.
if (sum2 == num1+1)
printf("(%d, %d)\n", num1, num2);
}
}
}
// Driver code
int main()
{
int n = 10000;
BetrothedNumbers(n);
return 0;
}
Java
// JAVA program to find Betrothed number
// pairs such that one of the numbers is
// smaller than a given number n.
import java.io.*;
class GFG{
static void BetrothedNumbers(int n)
{
for (int num1 = 1; num1 < n; num1++) {
// Calculate sum of num1's divisors
int sum1 = 1; // 1 is always a divisor
// i=2 because we don't want to include
// 1 as a divisor.
for (int i = 2; i * i <= num1; i++)
{
if (num1 % i == 0) {
sum1 += i;
// we do not want to include
// a divisor twice
if (i * i != num1)
sum1 += num1 / i;
}
}
// Now check if num2 is the sum of
// divisors of num1, so only the num
// that equals to sum of divisors of
// num1 is a nominee for num1.
/* This if is for not to make a
duplication of the nums, because
if sum1 is smaller than num1, this
means that we have already checked
the smaller one.*/
if (sum1 > num1)
{
int num2 = sum1 - 1;
int sum2 = 1;
for (int j = 2; j * j <= num2; j++)
{
if (num2 % j == 0) {
sum2 += j;
if (j * j != num2)
sum2 += num2 / j;
}
}
// checks if the sum divisors of
// num2 is equal to num1.
if (sum2 == num1+1)
System.out.println("(" + num1 +
", " + num2 + ")");
}
}
}
// Driver code
public static void main(String args[])
{
int n = 10000;
BetrothedNumbers(n);
}
}
// This code is contributed by Nikita Tiwari.
Python
# Python program to find Betrothed number pairs
# such that one of the numbers is smaller than
# a given number n.
def BetrothedNumbers(n) :
for num1 in range (1,n) :
# Calculate sum of num1's divisors
sum1 = 1 # 1 is always a divisor
# i=2 because we don't want to include
# 1 as a divisor.
i = 2
while i * i <= num1 :
if (num1 % i == 0) :
sum1 = sum1 + i
# we do not want to include
# a divisor twice
if (i * i != num1) :
sum1 += num1 / i
i =i + 1
# Now check if num2 is the sum of
# divisors of num1, so only the num
# that equals to sum of divisors of
# num1 is a nominee for num1.
# This if is for not to make a
#duplication of the nums, because
#if sum1 is smaller than num1, this
#means that we have already checked
#the smaller one.
if (sum1 > num1) :
num2 = sum1 - 1
sum2 = 1
j = 2
while j * j <= num2 :
if (num2 % j == 0) :
sum2 += j
if (j * j != num2) :
sum2 += num2 / j
j = j + 1
# checks if the sum divisors of
# num2 is equal to num1.
if (sum2 == num1+1) :
print ('('+str(num1)+', '+str(num2)+')')
# Driver code
n = 10000
BetrothedNumbers(n)
# This code is contributed by Nikita Tiwari.
C#
// C# program to find Betrothed
// number pairs such that one
// of the numbers is smaller
// than a given number n.
using System;
class GFG
{
static void BetrothedNumbers(int n)
{
for (int num1 = 1; num1 < n; num1++)
{
// Calculate sum of
// num1's divisors
// 1 is always a divisor
int sum1 = 1;
// i=2 because we don't want
// to include 1 as a divisor.
for (int i = 2; i * i <= num1; i++)
{
if (num1 % i == 0)
{
sum1 += i;
// we do not want to include
// a divisor twice
if (i * i != num1)
sum1 += num1 / i;
}
}
// Now check if num2 is the
// sum of divisors of num1,
// so only the num that equals
// to sum of divisors of num1
// is a nominee for num1.
/* This if is for not to
make a duplication of the
nums, because if sum1 is
smaller than num1, this
means that we have already
checked the smaller one.*/
if (sum1 > num1)
{
int num2 = sum1 - 1;
int sum2 = 1;
for (int j = 2; j * j <= num2; j++)
{
if (num2 % j == 0)
{
sum2 += j;
if (j * j != num2)
sum2 += num2 / j;
}
}
// checks if the sum divisors
// of num2 is equal to num1.
if (sum2 == num1 + 1)
Console.WriteLine("(" + num1 +
", " + num2 + ")");
}
}
}
// Driver code
public static void Main()
{
int n = 10000;
BetrothedNumbers(n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find Betrothed number pairs
// such that one of the numbers is smaller than
// a given number n.
function BetrothedNumbers($n)
{
for ( $num1 = 1; $num1 < $n; $num1++) {
// Calculate sum of num1's divisors
// 1 is always a divisor
$sum1 = 1;
// i=2 because we don't want to include
// 1 as a divisor.
for ( $i = 2; $i * $i <= $num1; $i++)
{
if ($num1 % $i == 0) {
$sum1 += $i;
// we do not want to include
// a divisor twice
if ($i * $i != $num1)
$sum1 += $num1 / $i;
}
}
// Now check if num2 is the sum of
// divisors of num1, so only the num
// that equals to sum of divisors of
// num1 is a nominee for num1.
/* This if is for not to make a
duplication of the nums, because
if sum1 is smaller than num1, this
means that we have already checked
the smaller one.*/
if ($sum1 > $num1)
{
$num2 = $sum1 - 1;
$sum2 = 1;
for ($j = 2; $j * $j <= $num2; $j++)
{
if ($num2 % $j == 0) {
$sum2 += $j;
if ($j * $j != $num2)
$sum2 += $num2 / $j;
}
}
// checks if the sum divisors of
// num2 is equal to num1.
if ($sum2 == $num1+1)
echo"(",$num1," ",$num2,")\n";
}
}
}
// Driver code
$n = 10000;
BetrothedNumbers($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find Betrothed number pairs
// such that one of the numbers is smaller than
// a given number n.
function BetrothedNumbers(n)
{
for (let num1 = 1; num1 < n; num1++)
{
// Calculate sum of num1's divisors
let sum1 = 1; // 1 is always a divisor
// i=2 because we don't want to include
// 1 as a divisor.
for (let i = 2; i * i <= num1; i++)
{
if (num1 % i == 0) {
sum1 += i;
// we do not want to include
// a divisor twice
if (i * i != num1)
sum1 += parseInt(num1 / i);
}
}
// Now check if num2 is the sum of
// divisors of num1, so only the num
// that equals to sum of divisors of
// num1 is a nominee for num1.
/* This if is for not to make a
duplication of the nums, because
if sum1 is smaller than num1, this
means that we have already checked
the smaller one.*/
if (sum1 > num1)
{
let num2 = sum1 - 1;
let sum2 = 1;
for (let j = 2; j * j <= num2; j++)
{
if (num2 % j == 0) {
sum2 += j;
if (j * j != num2)
sum2 += parseInt(num2 / j);
}
}
// checks if the sum divisors of
// num2 is equal to num1.
if (sum2 == (num1+1))
document.write(`(${num1}, ${num2})<br>`);
}
}
}
// Driver code
let n = 10000;
BetrothedNumbers(n);
// This code is contributed by rishavmahato348.
</script>
Producción :
(48, 75) (140, 195) (1050, 1925) (1575, 1648) (2024, 2295) (5775, 6128) (8892, 16587) (9504, 20735)
Complejidad temporal: O(n√n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Shlomi Elhaiani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA