Perfect Number Program in C++
Perfect Number in C++
In this post, we will learn different ways of coding Perfect Number in C++.
A perfect number is a number in which the sum of the proper positive divisors of the number is equal to the number itself.
For Example: 28 Divisors : 1 + 2 + 4 + 7 + 14 = 28
Methods
- Method 1: Iterating between [1, num] to find factors using for loop
- Method 2: Iterating between [1, num] to find factors using while loop
- Method 3: Iterating between [1, num/2] to find factors using
- Method 4: Using Function and Iterating between [1, num/2] to find factors using
- Method 5: Using Recursion
- Method 6: Iterating between [1, √num] to find factors
Method 1
For an input num
- Initialize sum = 0
- Using a for loop Iterate between [1, num-1] to find all divisors
- Add divisors to sum
- If sum == num, then it’s a perfect number
C++ Code:-
Run
#include <iostream>
using namespace std;
int main ()
{
int n = 28, sum = 0;
for(int i = 1; i < n; i++){
if(n % i == 0)
sum = sum + i;
}
if(sum == n)
cout << n << " is a perfect number";
else
cout << n << " is not a perfect number";
}
// Time complexity: O(N)
// Space complexity: O(1)Output
28 is a perfect number
Method 2
For an input num
- Initialize sum = 0
- Using a while loop Iterate between [1, num-1] to find all divisors
- Add divisors to sum
- If sum == num, then its a perfect number
C++ Code:-
Run
// Time complexity: O(N)
// Space complexity: O(1)
#include <iostream>
using namespace std;
int main ()
{
int num = 28, sum = 0;
int i = 1;
while(i < num)
{
// check if i is a divisor
if(num % i == 0)
sum = sum + i;
i++;
}
if(sum == num)
cout << num << " is a perfect number";
else
cout << num << " is not a perfect number";
return 0;
}
Output
28 is a perfect number
Method 3
- If we iterate b/w [1, num/2]
- All the divisors of the number can be found in this range
- Example : for 28: divisors {1, 2, 4, 7, 14}
- All are before num/2 i.e. 14
C++ Code:-
Run
// Time complexity: O(N)
// Space complexity: O(1)
#include <iostream>
using namespace std;
int main ()
{
int num = 28, sum = 0;
int i = 1;
// If we iterate b/w [1, num/2]
// all the divisors of the number can be found in this range
// example : for 28: divsors {1, 2, 4, 7, 14}
// all are before num/2 i.e. 14
while(i <= num/2)
{
// checking if i is a divisor
if(num % i == 0)
sum = sum + i;
i++;
}
if(sum == num)
cout << num << " is a perfect number";
else
cout << num << " is not a perfect number";
return 0;
}
Output
28 is a perfect number
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Method 4
This method uses the same approach as above. However, we do it via a function and a for loop.
C++ Code:-
Run
// Time complexity: O(N)
// Space complexity: O(1)
#include <iostream>
using namespace std;
bool checkPerfectNum(int n)
{
int sum = 0;
for (int i = 1; i <= n/2; i++){
if (n % i == 0)
sum = sum + i;
}
if (sum == n)
return true;
return false;
}
int main ()
{
int num = 28;
if(checkPerfectNum(num))
cout << num << " is a perfect number";
else
cout << num << " is not a perfect number";
return 0;
}
Output
28 is a perfect number
Method 5
This method uses recursion in C++
C++ Code:-
Run
// Time complexity: O(N)
// Space complexity: O(1)
// Auxiliary Space complexity: O(N) due to function call stack
#include <iostream>
using namespace std;
static int sum = 0;
int getSumDivisors(long num, int i)
{
// since, all factors can be found will num/2
// we will only check in this range
if(i <= num/2)
{
if(num % i ==0)
sum = sum + i;
i++;
// recursively call isPerfect
getSumDivisors(num, i);
}
//returns the sum
// when i becomes > num/2
return sum;
}
int main ()
{
int num = 28;
if(getSumDivisors(num, 1) == num)
cout << num << " is a perfect number";
else
cout << num << " is not a perfect number";
return 0;
}
Output
28 is a perfect number
Method 6
This method uses observations that all factors come in pairs.
All Factors come in pairs
For n = a * b (For each a there exists a unique b)
Example 1 : 100
(1,100), (2, 50), (4, 25), (5, 20), (10, 100)
Example 2 : 28
(1, 28), (2, 14), (4, 7)
Note : We will need to ignore pair of 1. As it will be the number itself.
Example 1 : 100
(1,100), (2, 50), (4, 25), (5, 20), (10, 100)
Example 2 : 28
(1, 28), (2, 14), (4, 7)
Note : We will need to ignore pair of 1. As it will be the number itself.
Shorten the Loop
We can shorten the loop running between [1, num] to [1, √num]
Since we will find all pairs before √num (n = sqrt(n) * sqrt(n))
Example: For 28, all pairs can be found before √28 = 5.2
Since we will find all pairs before √num (n = sqrt(n) * sqrt(n))
Example: For 28, all pairs can be found before √28 = 5.2
C++ Code:-
Run
#include <iostream>
#include <math.h>
using namespace std;
int getDivisorsSum(int n)
{
int sum = 0;
for(int i = 1; i < sqrt(n); i++)
{
if (n % i == 0)
{
// For n : (1, n) will always be pair of divisor
// acc to def., we must ignore adding num itself as divisor
// when calculating for perfect number
if(i == 1)
sum = sum + i;
// Example For 100 (10,10) will be one pair
// But, we should add value to the sum just once
else if(i == n/i)
sum = sum + i;
// add both pairs as divisors
// For any divisor i, n/i will also be a divisor
else
sum = sum + i + n/i;
}
}
return sum;
}
int main ()
{
int n = 28, sum = 0;
if(n == getDivisorsSum(n))
cout << n << " is a perfect number";
else
cout << n << " is not a perfect number";
}
// Time complexity: O(sqrt(N))
// Space complexity: O(1)Output
28 is a perfect number
- Positive or Negative number: C | C++ | Java | Python
- Even or Odd number: C | C++ | Java | Python
- Sum of First N Natural numbers: C | C++ | Java | Python
- Sum of N natural numbers: C | C++ | Java | Python
- Sum of numbers in a given range: C | C++ | Java | Python
- Greatest of two numbers: C | C++ | Java | Python
- Greatest of the Three numbers: C | C++ | Java | Python
- Leap year or not: C | C++ | Java | Python
- Prime number: C | C++ | Java | Python
- Prime number within a given range: C | C++ | Java | Python
- Sum of digits of a number: C | C++ | Java | Python
- Reverse of a number : C | C++ | Java | Python
- Palindrome number: C | C++ | Java | Python
- Armstrong number : C | C++ | Java | Python
- Armstrong number in a given range : C | C++ | Java | Python
- Fibonacci Series upto nth term : C | C++ | Java | Python
- Find the Nth Term of the Fibonacci Series : C | C++ | Java | Python
- Factorial of a number : C | C++ | Java | Python
- Power of a number : C | C++ | Java | Python
- Factor of a number : C | C++ | Java | Python
- Strong number : C | C++ | Java | Python
- Perfect number : C | C++ | Java | Python
- Automorphic number : C | C++ | Java | Python
- Harshad number : C | C++ | Java | Python
- Abundant number : C| C++ | Java | Python
- Friendly pair : C | C++ | Java | Python
Login/Signup to comment
#include
using namespace std;
int main(int argc, char const *argv[])
{
int n;
cout << "enter the number" <> n;
int ans = 0;
for (int i = 1; i < n; i++)
{
if (n % i == 0)
{
ans = ans + i;
}
}
if (n == ans)
{
cout << n << " is a perfect number " << endl;
}
else
cout << n << " is not a perfect number " << endl;
return 0;
}