A number is a Superabundant Number if sigma(n)/n > sigma(m)/m for all m < n, where sigma is the sum of the divisors of n.
1, 2, 4, 6, 12, 24, 36, 48…
Check if N is a Superabundant number
Given a number N, the task is to check if N is a Superabundant Number or not. If N is a Superabundant Number then print “Yes” else print “No”.
Examples:
Input: N = 4
Output: Yes
Explanation:
sigma(4)/4 = 7/4 = 1.75
sigma(1)/1 = 1/1 = 1
sigma(2)/2 = 3/2 = 1.5
sigma(3)/3 = 4/3 = 1.333333
sigma(n)/n > sigma(m)/m for all m < nInput: N = 10
Output: No
Approach: For all numbers i from 1 till less than N check if sigma(n)/n > sigma(m)/m then return false otherwise return true at last.
For Example:
If N = 4, sigma(4)/4 = 7/4 = 1.75
for i = 1 to 3
sigma(1)/1 = 1/1 = 1
sigma(2)/2 = 3/2 = 1.5
sigma(3)/3 = 4/3 = 1.333333
sigma(n)/n > sigma(m)/m for all m < n,
Hence return true at last
Below is the implementation of the above approach:
C++
// C++ implementation to check if // a number is Superabundant#include <bits/stdc++.h>using namespace std;// Function to calculate the sum of all// divisors of a given numberint sigma(int n){ if (n == 1) return 1; // Sum of divisors int result = 0; // find all divisors which divides 'num' for (int i = 2; i <= sqrt(n); i++) { // if 'i' is divisor of 'n' if (n % i == 0) { // if both divisors are same // then add it once else add // both if (i == (n / i)) result += i; else result += (i + n / i); } } // Add 1 and n to result as above loop // considers proper divisors greater // than 1. return (result + n + 1);}// Function to check if N is a // superabundant numberbool isSuperabundant(int N){ // to check all numbers from 1 to N for (float i = 1; i < N; i++) { float x = sigma(i) / i; float y = sigma(N) / (N * 1.0); if (x > y) return false; } return true;}// Driver codeint main(){ int N = 4; isSuperabundant(N) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// Java implementation to check if // a number is Superabundantclass GFG{ // Function to calculate the sum of all // divisors of a given number static int sigma(int n) { if (n == 1) return 1; // Sum of divisors int result = 0; // Find all divisors which divides 'num' for(int i = 2; i <= Math.sqrt(n); i++) { // If 'i' is divisor of 'n' if (n % i == 0) { // If both divisors are same // then add it once else add // both if (i == (n / i)) result += i; else result += (i + n / i); } } // Add 1 and n to result as above loop // considers proper divisors greater // than 1. return (result + n + 1); } // Function to check if N is a // superabundant number static boolean isSuperabundant(int N) { // To check all numbers from 1 to N for(double i = 1; i < N; i++) { double x = sigma((int)(i)) / i; double y = sigma((int)(N)) / (N * 1.0); if (x > y) return false; } return true; } // Driver code public static void main(String[] args) { int N = 4; if(isSuperabundant(N)) System.out.print("Yes\n"); else System.out.print("No\n"); } } // This code is contributed by shubham |
Python3
# Python3 implementation to check if # a number is Superabundant # Function to calculate the sum of all# divisors of a given numberdef sigma(n): if (n == 1): return 1 # Sum of divisors result = 0 # Find all divisors which divides 'num' for i in range(2, pow(n, 1 // 2)): # If 'i' is divisor of 'n' if (n % i == 0): # If both divisors are same # then add it once else add # both if (i == (n / i)): result += i else: result += (i + n / i) # Add 1 and n to result as above loop # considers proper divisors greater # than 1. return (result + n + 1)# Function to check if N is a# superabundant numberdef isSuperabundant(N): # To check all numbers from 1 to N for i in range(1, N): x = sigma((int)(i)) / i y = sigma((int)(N)) / (N * 1.0) if (x > y): return False return True# Driver codeif __name__ == '__main__': N = 4 if (isSuperabundant(N) != True): print("Yes") else: print("No")# This code is contributed by shikhasingrajput |
C#
// C# implementation to check if // a number is Superabundantusing System;class GFG{ // Function to calculate the sum of // all divisors of a given number static int sigma(int n) { if (n == 1) return 1; // Sum of divisors int result = 0; // Find all divisors which divides 'num' for(int i = 2; i <= Math.Sqrt(n); i++) { // If 'i' is divisor of 'n' if (n % i == 0) { // If both divisors are same // then add it once else add // both if (i == (n / i)) result += i; else result += (i + n / i); } } // Add 1 and n to result as above loop // considers proper divisors greater // than 1. return (result + n + 1); } // Function to check if N is a // superabundant number static bool isSuperabundant(int N) { // To check all numbers from 1 to N for(double i = 1; i < N; i++) { double x = sigma((int)(i)) / i; double y = sigma((int)(N)) / (N * 1.0); if (x > y) return false; } return true; } // Driver code public static void Main(String[] args) { int N = 4; if(isSuperabundant(N)) Console.Write("Yes\n"); else Console.Write("No\n"); } } // This code is contributed by amal kumar choubey |
Javascript
<script>// Javascript implementation to check if // a number is Superabundant// Function to calculate the sum of all// divisors of a given numberfunction sigma(n){ if (n == 1) return 1; // Sum of divisors var result = 0; // find all divisors which divides 'num' for (var i = 2; i <= Math.sqrt(n); i++) { // if 'i' is divisor of 'n' if (n % i == 0) { // if both divisors are same // then add it once else add // both if (i == (n / i)) result += i; else result += (i + n / i); } } // Add 1 and n to result as above loop // considers proper divisors greater // than 1. return (result + n + 1);}// Function to check if N is a // superabundant numberfunction isSuperabundant(N){ // to check all numbers from 1 to N for (var i = 1; i < N; i++) { var x = sigma(i) / i; var y = sigma(N) / (N * 1.0); if (x > y) return false; } return true;}// Driver codevar N = 4;isSuperabundant(N) ? document.write( "Yes") : document.write("No");</script> |
Output:
Yes
Time Complexity: O(n)
Share your thoughts in the comments
