You are here:

C++/Perfect Number

Advertisement


Question
Dear Vijayan,

A perfect number is a number which sum of all its divisors equals the number. for example for 6, we have: 1 + 2 + 3 = 6

A program to find all the perfect numbers is somehow easy to write. The problem appears when it takes too much time to find the 5th, 6th, 7th, ... perfect number.

I have already a list of first 10 perfect numbers. But I want to manually find them using c++ so much quickly.

With best regards, Mojtaba

Answer
A Mersenne number is a positive integer that is one less than a power of two. That is, a number of the form

2 ^ p - 1

where p is an integer and the symbol ^ indicates raising to the power.

A Mersenne prime is a Mersenne number that is prime.

As of now, only 47 Mersenne primes are known:
http://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes

In the 18th century, Leonhard Euler proved that the formula

2 ^ (p − 1) * ( 2 ^ p − 1 )

will yield all the even perfect numbers. Thus, there is a concrete one-to-one association between even perfect numbers and Mersenne primes.

It is unknown if there are any odd perfect numbers. However, it has been shown that there are no perfect numbers with fewer than 300 decimal digits. That is, any odd perfect number N must satisfy N > 10 ^ 300.

Since you program only needs to print all perfect numbers less than 50000, the numbers are very few.

The first ten perfect numbers are given by:

2 ^ (p − 1) * ( 2 ^ p − 1 )  for p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89

The fifth perfect number is 33550336 p == 13, N == 2 ^ 12 * ( 2 ^ 13 − 1 )

So there are only four perfect numbers less than 50000, and you can generate them very fast by evaluating

2 ^ (p − 1) * ( 2 ^ p − 1 )  for p = 2, 3, 5, 7  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.