Java Program to Check if a Given Number is Perfect Number
A number is said to be a perfect number if the sum of its proper divisors ( i.e. all positive divisors excluding the number itself )is equal to that number itself. Aliquot sum is the sum of divisors of a number, excluding the number itself. Hence, a number is a perfect number only if it is equal to its aliquot sum. All known perfect numbers are even. In this article, we will learn how to Check Perfect Numbers in Java.
Example 1:
n = 9
Proper Divisors of 9 are 1 and 3.
Sum = 1+3 = 4 ≠ 9
⇒ 9 is not a perfect number.Example 2:
n = 6
Proper Divisors of 6 are 1, 2 and 3.
Sum = 1+2+3 = 6 = 6
⇒ 6 is a perfect number
So, we basically have to find the sum of the proper divisors of a number.
1. Using Loop to Check Perfect Number in Java
A Simple Solution is to go through every number from 1 to n-1 and check if it is a divisor and if it is, then add it in the sum variable and at the end check if the sum is equal to the number itself, then it is a perfect number otherwise not.
Below is the implementation of the above method:
Java
// Java program to check if a given // number is perfect or not class GFG { // Returns true if n is perfect static boolean isPerfect( int n) { // 1 is not a perfect number if (n == 1 ) return false ; // sum will store the sum of proper divisors // As 1 is a proper divisor for all numbers // initialised sum with 1 int sum = 1 ; // Looping through the numbers to check if they are // divisors or not for ( int i = 2 ; i < n; i++) { if (n % i == 0 ) { sum += i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n) return true ; return false ; } // Driver program public static void main(String[] args) { int n = 6 ; // Call isPerfect function to // check if the number is perfect or not. if (isPerfect(n)) System.out.println(n + " is a perfect number" ); else System.out.println( n + " is not a perfect number" ); } } |
6 is a perfect number
The complexity of the above method
- Time Complexity: O(n)
2. Using Square root to Check Perfect Number in Java
An Efficient Solution is to go through numbers till the square root of n.
If i is a divisor then n/i is also a divisor.
Java
// Java program to check if a given // number is perfect or not class GFG { // Returns true if n is perfect static boolean isPerfect( int n) { // 1 is not a perfect number if (n == 1 ) return false ; // sum will store the sum of proper divisors // As 1 is a proper divisor for all numbers // initialised sum with 1 int sum = 1 ; // Looping through the numbers to check if they are // divisors or not for ( int i = 2 ; i * i <= n; i++) { if (n % i == 0 ) { // n is a perfect square // let's take 25 // we need to add 5 only once // sum += i + n / i will add it twice if (i * i == n) sum += i; else sum += i + (n / i); } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n) return true ; return false ; } // Driver program public static void main(String[] args) { int n = 6 ; // Call isPerfect function to // check if the number is perfect or not. if (isPerfect(n)) System.out.println(n + " is a perfect number" ); else System.out.println( n + " is not a perfect number" ); } } |
6 is a perfect number
The complexity of the above method
Time Complexity: O(√n)
3. Recursive Approach to Check Perfect Number in Java
Below is the implement the above method:
Java
// Java Program to implement Perfect // Number using Recursion import java.util.*; // Driver Class public class GFG { static long sum = 0 ; static long isPerfect( long num, int i) { // Base Condition if (i <= num / 2 ) { if (num % i == 0 ) { sum = sum + i; } // after each iteration, increments the value of // variable i by 1 i++; // recursive call isPerfect(num, i); } // returns the sum of factors return sum; } // main function public static void main(String args[]) { long number = 28 , s; int i = 1 ; s = isPerfect(number, i); // compares sum with the number if (s == number) // prints if the s and number are equal System.out.println(number + " is a perfect number" ); else // prints if s and number are not equal System.out.println( number + " is not a perfect number" ); } } |
28 is a perfect number
The complexity of the above method
Time Complexity: O(n)