C/C++ Program to Print First n Perfect Numbers

Write a program in C/C++ to print first n perfect numbers.

For example,

Input
3
Output
6 28 496

What is a perfect numbers?

A Perfect number is a positive number such that the sum of the proper divisors of the number is equal to the number itself. For example, the proper divisors of 6 are { 1 , 2 , 3 }. 1 + 2 + 3 = 6, therefore, 6 is a perfect number.

Program to Print First n Perfect Numbers: Brute Force Method

Steps

  1. Let n be the input number.
  2. Set i = 1.
  3. Repeat the following steps while n > 0
    • Check if i is perfect or not.
    • If i is perfect, print i and decrement n. If i is not perfect, do nothing.
    • Increment i.

In the brute force method, we are basically iterating all numbers starting from 1 and checking if the number is perfect or not. If the number is perfect, we print it on the screen. The loop stops after printing n numbers.

#include <stdio.h>
#include <math.h>

// function to check if a number - n is perfect or not
// returns 1 if n is perfect
// returns 0 if n is not perfect
int isPerfect(long long int n) {

	long long int dsum = 0;	// sum of divisors
	long long int i;

	// the loop finds all diviors of n
	for (i = 1; i <= sqrt(n); ++i) {
		if (n % i == 0) {

			if (i == n / i) {
				dsum += i;
			}
			else {
				dsum += i;
				dsum += n / i;
			}

		}
	}

	// we are only counting proper diviors of n (less than n)
	// so we need to substract n from the final sum
	dsum = dsum - n;

	if (dsum == n) return 1;
	else		return 0;

}

int main() {

	long long int n, i, temp;
	printf("Enter n: ");
	scanf("%d", &n);

	i = 1;

	// iterating all numbers from 1
	// and checking if the number is perfect or not
	while (n > 0) {

		if (isPerfect(i) == 1) {
			printf("%d ", i);
			n = n - 1;
		}
		i = i + 1;

	}

	printf("\n");

}

Output

Enter n: 4
6 28 496 8128

Program to Print First n Perfect Numbers: Efficient Method

The previous method works fine if the value of n is small ( n < 5 ). But if n is large then the program will take a long time to find n perfect numbers. For example, the value of the 6th perfect number is 8589869056. Thus, calculating perfect numbers using the brute force technique is not feasible.

We can find perfect numbers efficiently using the fact that every perfect number is in the form 2^{p-1}*(2^{p}-1) where p is a prime number. Instead of iterating each number from 1 and checking for the perfect numbers, we instead search for prime numbers and check if 2^{p-1}*(2^{p}-1) is perfect or not.

Note: If p is prime then 2^{p-1}*(2^{p}-1) is not necessary perfect.

#include <stdio.h>
#include <math.h>

// function to check if a number - n is perfect or not
// returns 1 if n is perfect
// returns 0 if n is not perfect
int isPerfect(long long int n) {

	long long int dsum = 0;	// sum of divisors
	long long int i;

	// the loop finds all diviors of n
	for (i = 1; i <= sqrt(n); ++i) {
		if (n % i == 0) {

			if (i == n / i) {
				dsum += i;
			}
			else {
				dsum += i;
				dsum += n / i;
			}

		}
	}

	// we are only counting proper diviors of n (less than n)
	// so we need to substract n from the final sum
	dsum = dsum - n;

	if (dsum == n) return 1;
	else		return 0;

}

// function check if a number - n is prime or not
// returns 1 if n is prime
// returns 0 if n is not prime
int isPrime(long long int n) {

	if (n == 1)
		return 0;

	for (int i = 2; i <= sqrt(n); ++i) {
		if (n % i == 0)
			return 0;
	}
	return 1;

}

int main() {

	long long int n, i, temp;
	printf("Enter n: ");
	scanf("%d", &n);

	i = 1;

	// iterating all numbers from 1
	// and checking if the number is perfect or not
	while (n > 0) {

		if (isPrime(i) == 1) {
			temp = pow(2, i - 1) * (pow(2, i) - 1);
			if (isPerfect(temp) == 1) {
				printf("%d ", temp);
				n = n - 1;
			}
		}
		i = i + 1;

	}

	printf("\n");

}

Ouput

Enter n: 5
6 28 496 8128 33550336

We can further optimize the program using the following techniques:-

  1. Use Sieve of Eratosthenes to efficiently find prime numbers.
  2. We know that perfect number is in form 2^{p-1}*(2^{p}-1). Thus, we can optimize the code to find the sum of divisors of a number more efficiently.

Read

References

Leave a Comment