Números de Ruth-Aarón

Se dice que un número N es un número de Ruth-Aaron si la suma de los divisores primos de N es igual a la suma de los divisores primos de N+1 .
Los primeros números de Ruth-Aaron son:

5, 24, 49, 77, 104, 153, 369, 492, 714……..

Comprobar si N es un número de Ruth-Aaron

Dado un número N , la tarea es encontrar si este número es el número de Ruth-Aaron o no. 
Ejemplos: 
 

Entrada: N = 714 
Salida: SI
Entrada: N = 25 
Salida: No

Enfoque : la idea es encontrar la suma de todos los divisores propios de N y N + 1 y comprobar si las sumas de los divisores propios de N y N+1 son iguales o no. Si la suma de los divisores propios de N y N+1 es igual, entonces el número es el número de Ruth-Aaron.
Por ejemplo: 
 

Para N = 714 
Suma de Divisores Propios de N (714) = 2 + 3 + 7 + 17 = 29 
Suma de Divisores Propios de N+1 (715) = 5 + 11 + 13 = 29
Por lo tanto, N es un Ruth-Aaron número.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find prime divisors of
// all numbers from 1 to N
int Sum(int N)
{
    int SumOfPrimeDivisors[N + 1] = { 0 };
 
    for (int i = 2; i <= N; ++i) {
 
        // if the number is prime
        if (!SumOfPrimeDivisors[i]) {
 
            // add this prime to all
            // it's multiples
            for (int j = i; j <= N; j += i) {
 
                SumOfPrimeDivisors[j] += i;
            }
        }
    }
    return SumOfPrimeDivisors[N];
}
 
// Function to check Ruth-Aaron number
bool RuthAaronNumber(int n)
{
    if (Sum(n) == Sum(n + 1))
        return true;
    else
        return false;
}
 
// Driver code
int main()
{
 
    int N = 714;
    if (RuthAaronNumber(N)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    return 0;
}

// Java implementation of the above approach
class GFG{
     
// Function to find prime divisors of
// all numbers from 1 to N
static int Sum(int N)
{
    int SumOfPrimeDivisors[] = new int[N + 1];
 
    for (int i = 2; i <= N; ++i)
    {
 
        // if the number is prime
        if (SumOfPrimeDivisors[i] == 1)
        {
 
            // add this prime to all
            // it's multiples
            for (int j = i; j <= N; j += i)
            {
                SumOfPrimeDivisors[j] += i;
            }
        }
    }
    return SumOfPrimeDivisors[N];
}
 
// Function to check Ruth-Aaron number
static boolean RuthAaronNumber(int n)
{
    if (Sum(n) == Sum(n + 1))
        return true;
    else
        return false;
}
 
// Driver code
public static void main (String[] args)
{
 
    int N = 714;
    if (RuthAaronNumber(N))
    {
        System.out.print("Yes");
    }
    else
    {
        System.out.print("No");
    }
}
}
 
// This code is contributed by Ritik Bansal

# Python3 implementation of the above approach
 
# Function to find prime divisors of
# all numbers from 1 to N
def Sum(N):
 
    SumOfPrimeDivisors = [0] * (N + 1)
 
    for i in range(2, N + 1):
 
        # If the number is prime
        if (SumOfPrimeDivisors[i] == 0):
 
            # Add this prime to all
            # it's multiples
            for j in range(i, N + 1, i):
                SumOfPrimeDivisors[j] += i
 
    return SumOfPrimeDivisors[N]
 
# Function to check Ruth-Aaron number
def RuthAaronNumber(n):
 
    if (Sum(n) == Sum(n + 1)):
        return True
    else:
        return False
 
# Driver code
N = 714
 
if (RuthAaronNumber(N)):
    print("Yes")
else:
    print("No")
 
# This code is contributed by vishu2908

// C# implementation of the above approach
using System;
class GFG{
     
// Function to find prime divisors of
// all numbers from 1 to N
static int Sum(int N)
{
    int []SumOfPrimeDivisors = new int[N + 1];
 
    for (int i = 2; i <= N; ++i)
    {
 
        // if the number is prime
        if (SumOfPrimeDivisors[i] == 1)
        {
 
            // add this prime to all
            // it's multiples
            for (int j = i; j <= N; j += i)
            {
                SumOfPrimeDivisors[j] += i;
            }
        }
    }
    return SumOfPrimeDivisors[N];
}
 
// Function to check Ruth-Aaron number
static bool RuthAaronNumber(int n)
{
    if (Sum(n) == Sum(n + 1))
        return true;
    else
        return false;
}
 
// Driver code
public static void Main()
{
    int N = 714;
    if (RuthAaronNumber(N))
    {
        Console.Write("Yes");
    }
    else
    {
        Console.Write("No");
    }
}
}
 
// This code is contributed by Code_Mech

<script>
// Javascript implementation of the above approach
 
    // Function to find prime divisors of
    // all numbers from 1 to N
    function Sum( N) {
        let SumOfPrimeDivisors = Array(N + 1).fill(0);
 
        for ( let i = 2; i <= N; ++i) {
 
            // if the number is prime
            if (SumOfPrimeDivisors[i] == 1) {
 
                // add this prime to all
                // it's multiples
                for (let  j = i; j <= N; j += i) {
                    SumOfPrimeDivisors[j] += i;
                }
            }
        }
        return SumOfPrimeDivisors[N];
    }
 
    // Function to check Ruth-Aaron number
    function RuthAaronNumber( n) {
        if (Sum(n) == Sum(n + 1))
            return true;
        else
            return false;
    }
 
    // Driver code
    let N = 714;
    if (RuthAaronNumber(N)) {
        document.write("Yes");
    } else {
        document.write("No");
    }
 
// This code is contributed by Rajput-Ji
</script>

Yes

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)

Referencia: https://oeis.org/A006145