Bei einer gegebenen Zahl n müssen wir prüfen, ob n eine aufstrebende Zahl ist oder nicht. Die Zahl n wird eine aufstrebende Zahl genannt, wenn ihre aliquote Folge in einer vollkommenen Zahl endet und sie selbst keine vollkommene Zahl ist. Die ersten aufstrebenden Zahlen sind: 25, 95, 119, 143, 417, 445, 565, 608, 650, 652….

Beispiele:  

Input : 25
Output : Yes.
Explanation : Terminating number of 
aliquot sequence of 25 is 6 which is 
perfect number.

Input :  24
Output : No.
Explanation : Terminating number of 
aliquot sequence of 24 is 0 which is 
not a perfect number.

Vorgehensweise: Zuerst finden wir die Endzahl der aliquoten Folge der gegebenen Eingabe und prüfen dann, ob es sich um eine perfekte Zahl handelt oder nicht (per Definition). Unten ist die Implementierung zum Prüfen einer aufstrebenden Zahl angegeben.  

// C++ implementation to check whether
// a number is aspiring or not
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate sum of all proper
// divisors
int getSum(int n)
{
    int sum = 0; // 1 is a proper divisor
 
    // Note that this loop runs till square root
    // of n
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
 
            // If divisors are equal, take only one
            // of them
            if (n / i == i)
                sum = sum + i;
 
            else // Otherwise take both
            {
                sum = sum + i;
                sum = sum + (n / i);
            }
        }
    }
 
    // calculate sum of all proper divisors only
    return sum - n;
}
 
// Function to get last number of Aliquot Sequence.
int getAliquot(int n)
{
    unordered_set<int> s;
    s.insert(n);
 
    int next = 0;
    while (n > 0) {
 
        // Calculate next term from previous term
        n = getSum(n);
 
        if (s.find(n) != s.end())
            return n;       
 
        s.insert(n);
    }
    return 0;
}
 
// Returns true if n is perfect
bool isPerfect(int n)
{
    // To store sum of divisors
    long long int sum = 1;
 
    // Find all divisors and add them
    for (long long int i = 2; i * i <= n; i++)
        if (n % i == 0)
            sum = sum + i + n / i;
 
    // If sum of divisors is equal to
    // n, then n is a perfect number
    if (sum == n && n != 1)
        return true;
 
    return false;
}
 
// Returns true if n is aspiring
// else returns false
bool isAspiring(int n)
{
    // checking condition for aspiring
    int alq = getAliquot(n);
    if (isPerfect(alq) && !isPerfect(n))
        return true;
    else
        return false;
}
 
// Driver program
int main()
{
    int n = 25;
    if (isAspiring(n))
        cout << "Aspiring" << endl;
    else
        cout << "Not Aspiring" << endl;
 
    return 0;
}

// Java implementation to check whether
// a number is aspiring or not
import java.util.*;
 
class GFG
{
 
    // Function to calculate sum of
    //  all proper divisors
    static int getSum(int n)
    {
        int sum = 0; // 1 is a proper divisor
 
        // Note that this loop runs till 
        // square root of n
        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0)
            {
 
                // If divisors are equal,
                // take only one of them
                if (n / i == i)
                {
                    sum = sum + i;
                }
                else // Otherwise take both
                {
                    sum = sum + i;
                    sum = sum + (n / i);
                }
            }
        }
 
        // calculate sum of all
        // proper divisors only
        return sum - n;
    }
 
    // Function to get last number
    // of Aliquot Sequence.
    static int getAliquot(int n)
    {
        TreeSet<Integer> s = new TreeSet<Integer>();
        s.add(n);
 
        int next = 0;
        while (n > 0)
        {
 
            // Calculate next term from previous term
            n = getSum(n);
 
            if (s.contains(n) & n != s.last())
            {
                return n;
            }
 
            s.add(n);
        }
        return 0;
    }
 
    // Returns true if n is perfect
    static boolean isPerfect(int n)
    {
        // To store sum of divisors
        int sum = 1;
 
        // Find all divisors and add them
        for (int i = 2; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                sum = sum + i + n / i;
            }
        }
 
        // If sum of divisors is equal to
        // n, then n is a perfect number
        if (sum == n && n != 1)
        {
            return true;
        }
 
        return false;
    }
 
    // Returns true if n is aspiring
    // else returns false
    static boolean isAspiring(int n)
    {
         
        // checking condition for aspiring
        int alq = getAliquot(n);
        if (isPerfect(alq) && !isPerfect(n))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 25;
        if (isAspiring(n))
        {
            System.out.println("Aspiring");
        }
        else
        {
            System.out.println("Not Aspiring");
        }
    }
}
 
/* This code has been contributed
by PrinciRaj1992*/

# Python3 implementation to check whether
# a number is aspiring or not
 
# Function to calculate sum of all proper
# divisors
def getSum(n):
   
  # 1 is a proper divisor
  sum = 0
   
  # Note that this loop runs till
  # square root of n
  for i in range(1, int((n) ** (1 / 2)) + 1):
    if not n % i:
       
      # If divisors are equal, take
      # only one of them
      if n // i == i:
        sum += i
         
      # Otherwise take both
      else:
        sum += i
        sum += (n // i)
         
  # Calculate sum of all proper
  # divisors only
  return sum - n
 
# Function to get last number
# of Aliquot Sequence.
def getAliquot(n):
   
  s = set()
  s.add(n)
  next = 0
   
  while (n > 0):
     
    # Calculate next term from
    # previous term
    n = getSum(n)
     
    if n not in s:
      return n 
 
    s.add(n)
     
  return 0
 
# Returns true if n is perfect
def isPerfect(n):
   
  # To store sum of divisors
  sum = 1
   
  # Find all divisors and add them
  for i in range(2, int((n ** (1 / 2))) + 1):
    if not n % i:
      sum += (i + n // i)
       
  # If sum of divisors is equal to
  # n, then n is a perfect number
  if sum == n and n != 1:
    return True
   
  return False
 
# Returns true if n is aspiring
# else returns false
def isAspiring(n):
   
  # Checking condition for aspiring
  alq = getAliquot(n)
   
  if (isPerfect(alq) and not isPerfect(n)):
    return True
  else:
    return False
 
# Driver Code
n = 25
 
if (isAspiring(n)):
  print("Aspiring")
else:
  print("Not Aspiring")
 
# This code is contributed by rohitsingh07052

// C# implementation to check whether
// a number is aspiring or not
using System;
using System.Collections.Generic;
class GFG
{
 
    // Function to calculate sum of
    //  all proper divisors
    static int getSum(int n)
    {
        int sum = 0; // 1 is a proper divisor
 
        // Note that this loop runs till 
        // square root of n
        for (int i = 1; i <= (int)Math.Sqrt(n); i++)
        {
            if (n % i == 0)
            {
 
                // If divisors are equal,
                // take only one of them
                if (n / i == i)
                {
                    sum = sum + i;
                }
                else // Otherwise take both
                {
                    sum = sum + i;
                    sum = sum + (n / i);
                }
            }
        }
 
        // calculate sum of all
        // proper divisors only
        return sum - n;
    }
 
    // Function to get last number
    // of Aliquot Sequence.
    static int getAliquot(int n)
    {
        HashSet<int> s = new HashSet<int>();
        s.Add(n);
        while (n > 0)
        {
 
            // Calculate next term from previous term
            n = getSum(n);
            if (s.Contains(n))
            {
                return n;
            }
            s.Add(n);
        }
        return 0;
    }
 
    // Returns true if n is perfect
    static bool isPerfect(int n)
    {
        // To store sum of divisors
        int sum = 1;
 
        // Find all divisors and add them
        for (int i = 2; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                sum = sum + i + n / i;
            }
        }
 
        // If sum of divisors is equal to
        // n, then n is a perfect number
        if (sum == n && n != 1)
        {
            return true;
        }
 
        return false;
    }
 
    // Returns true if n is aspiring
    // else returns false
    static bool isAspiring(int n)
    {
         
        // checking condition for aspiring
        int alq = getAliquot(n);
        if (isPerfect(alq) && !isPerfect(n))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int n = 25;
        if (isAspiring(n))
        {
            Console.WriteLine("Aspiring");
        }
        else
        {
            Console.WriteLine("Not Aspiring");
        }
    }
}
 
// This code is contributed by subhammahato348

Aufstrebend

Zeitkomplexität: O(n)