Número de paciente perfecto

Posted on by Rudeus Greyrat

Un número totient perfecto es un número entero que es igual a la suma de sus totients iterados. El número total de pacientes perfecto se denota por  \varphi^i(n) . 
Por ejemplo: 
 

\varphi^i (9) = 6 , Ahora,  \varphi^i (6) = 2 ,  \varphi^i (2) = 1 y 9 == 6 + 2 + 1, Por lo tanto, 9 es un número tociente perfecto. 
 

Compruebe si N es un número de paciente perfecto

Dado un número entero N , la tarea es comprobar que N es un número de cliente perfecto.
Ejemplos: 
 

Entrada: N = 9 
Salida: Sí
Entrada: N = 10 
Salida: No 
 

Enfoque: La idea es encontrar el valor de Euler totient del número dado, supongamos que obtenemos el valor de Euler totient de N como V, luego encontraremos nuevamente el valor de Euler totient de V hasta que el nuevo valor de Euler totient V se convierta en 1. también mantendrá la suma de todos los valores de Euler Totient Value V que obtuvimos hasta ahora y verificará si la suma es igual a N o no. Si es igual, entonces el número dado es un número perfecto de Euler Totient.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation to find
// the number of digits in
// a Nth fibonacci number
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Totient
// number of the given value
int phi(int n)
{
    // Initialize result as n
    int result = n;
 
    // Consider all prime factors
    // of n and subtract their
    // multiples from result
    for (int p = 2; p * p <= n; ++p) {
         
        // Check if p is a prime factor.
        if (n % p == 0) {
             
            // If yes, then update N
            // and result
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }
 
    // If n has a prime factor
    // greater than sqrt(n)
    // (There can be at-most one
    // such prime factor)
    if (n > 1)
        result -= result / n;
    return result;
}
 
// Function to check if the number
// is a perfect totient number
int isPerfectTotientNum(int n)
{
    // store original value of n
    int temp = n;
    int sum = 0;
     
    // loop to calculate sum
    // of iterated totients
    while(n > 1){
        sum = sum + phi(n);
        n = phi(n);
    }
    // condition for Perfect
    // Totient Number
    if(sum == temp)
    return true;
     
    return false;
}
 
// Driver Code
int main()
{
    int n = 9;
    if(isPerfectTotientNum(n))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Java

// Java implementation to find the 
// number of digits in a Nth
// fibonacci number
class GFG{
 
// Function to find the Totient
// number of the given value
static int phi(int n)
{
     
    // Initialize result as n
    int result = n;
 
    // Consider all prime factors
    // of n and subtract their
    // multiples from result
    for(int p = 2; p * p <= n; ++p)
    {
         
       // Check if p is a prime factor
       if (n % p == 0)
       {
            
           // If yes, then update N
           // and result
           while (n % p == 0)
           {
               n /= p;
           }
           result -= result / p;
       }
    }
 
    // If n has a prime factor
    // greater than sqrt(n)
    // (There can be at-most one
    // such prime factor)
    if (n > 1)
        result -= result / n;
    return result;
}
 
// Function to check if the number
// is a perfect totient number
static boolean isPerfectTotientNum(int n)
{
     
    // Store original value of n
    int temp = n;
    int sum = 0;
     
    // Loop to calculate sum
    // of iterated totients
    while(n > 1)
    {
        sum = sum + phi(n);
        n = phi(n);
    }
     
    // Condition for Perfect
    // Totient Number
    if(sum == temp)
       return true;
     
    return false;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 9;
     
    if(isPerfectTotientNum(n))
    {
        System.out.println("Yes");
    }
    else
    {
        System.out.println("No");
    }
}
}
 
// This code is contributed by Ritik Bansal

Python3

# Python3 implementation to find
# the number of digits in
# a Nth fibonacci number
 
# Function to find the Totient
# number of the given value
def phi(n):
     
    # Initialize result as n
    result = n
 
    # Consider all prime factors
    # of n and subtract their
    # multiples from result
    for p in range(2, n):
        if p * p > n:
            break
 
        # Check if p is a prime factor.
        if (n % p == 0):
 
            # If yes, then update N
            # and result
            while (n % p == 0):
                n //= p
                 
            result -= result // p
 
    # If n has a prime factor
    # greater than sqrt(n)
    # (There can be at-most one
    # such prime factor)
    if (n > 1):
        result -= result // n
         
    return result
 
# Function to check if the number
# is a perfect totient number
def isPerfectTotientNum(n):
     
    # Store original value of n
    temp = n
    sum = 0
 
    # Loop to calculate sum
    # of iterated totients
    while (n > 1):
        sum = sum + phi(n)
        n = phi(n)
         
    # Condition for Perfect
    # Totient Number
    if (sum == temp):
        return True
 
    return False
 
# Driver Code
if __name__ == '__main__':
     
    n = 9
     
    if (isPerfectTotientNum(n)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

C#

// C# implementation to find the
// number of digits in a Nth
// fibonacci number
using System;
class GFG{
 
// Function to find the Totient
// number of the given value
static int phi(int n)
{
     
    // Initialize result as n
    int result = n;
 
    // Consider all prime factors
    // of n and subtract their
    // multiples from result
    for(int p = 2; p * p <= n; ++p)
    {
        
       // Check if p is a prime factor
       if (n % p == 0)
       {
            
           // If yes, then update N
           // and result
           while (n % p == 0)
           {
               n /= p;
           }
           result -= result / p;
       }
    }
 
    // If n has a prime factor
    // greater than sqrt(n)
    // (There can be at-most one
    // such prime factor)
    if (n > 1)
        result -= result / n;
    return result;
}
 
// Function to check if the number
// is a perfect totient number
static bool isPerfectTotientNum(int n)
{
     
    // Store original value of n
    int temp = n;
    int sum = 0;
     
    // Loop to calculate sum
    // of iterated totients
    while(n > 1)
    {
        sum = sum + phi(n);
        n = phi(n);
    }
     
    // Condition for Perfect
    // Totient Number
    if(sum == temp)
    return true;
     
    return false;
}
 
// Driver Code
public static void Main()
{
    int n = 9;
     
    if(isPerfectTotientNum(n))
    {
        Console.Write("Yes");
    }
    else
    {
        Console.Write("No");
    }
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
// Javascript implementation to find the 
// number of digits in a Nth
// fibonacci number
 
    // Function to find the Totient
    // number of the given value
    function phi( n)
    {
 
        // Initialize result as n
        let result = n;
 
        // Consider all prime factors
        // of n and subtract their
        // multiples from result
        for ( let p = 2; p * p <= n; ++p)
        {
 
            // Check if p is a prime factor
            if (n % p == 0)
            {
 
                // If yes, then update N
                // and result
                while (n % p == 0)
                {
                    n = parseInt(n/p);
                }
                result -= parseInt(result / p);
            }
        }
 
        // If n has a prime factor
        // greater than sqrt(n)
        // (There can be at-most one
        // such prime factor)
        if (n > 1)
            result -= parseInt(result / n);
        return result;
    }
 
    // Function to check if the number
    // is a perfect totient number
    function isPerfectTotientNum( n) {
 
        // Store original value of n
        let temp = n;
        let sum = 0;
 
        // Loop to calculate sum
        // of iterated totients
        while (n > 1) {
            sum = sum + phi(n);
            n = phi(n);
        }
 
        // Condition for Perfect
        // Totient Number
        if (sum == temp)
            return true;
 
        return false;
    }
 
    // Driver Code
    let n = 9;
 
    if (isPerfectTotientNum(n)) {
        document.write("Yes");
    } else {
        document.write("No");
    }
// This code is contributed by aashish1995
</script>
Producción: 

Yes

 

Complejidad de tiempo: O (n 1/2 )

Espacio Auxiliar: O(1)

Referencias: https://en.wikipedia.org/wiki/Perfect_totient_number
 

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *