C++/C++ Perfect Numbers
I just joined a programming club and we have to do problems to improve our knowledge from time to time. I am just beginning so I was wondering if you could help me out or at least get me in the right direction?
Write a program that will print all perfect numbers less than 50000. Your program will take a while to run so you should have it print a message occasionally to let you know that it is still working. Use only for loops, arrays, and if statements along with the basic C++ functions.
If you could help me with this it would be greatly appreciated.
Hello Kyle. A computer club is fantastic! I suppose you like puzzles and don't want the answer given right away. You can stop reading when you feel you have enough to get started.
You probably know what perfect numbers are, but lets review. A number is perfect if all its factors, not including the number itself, add up to the number. For example, 6 is perfect, because its factors 1,2,3 add up to 6. The number 1 is not perfect because it doesn't fit the definition. Obviously, 1 is always a factor.
The first perfect numbers are 6, 28, 496, 8128, 33550336. It takes a long time to reach the 5'th one.
Another interesting fact is that nobody knows of any odd perfect numbers, although it has not been proven that odd numbers cannot be perfect. You can read about that at http://en.wikipedia.org/wiki/Perfect_number
So obviously you need a loop to generate all the candidate numbers, and you need a second loop which will generate all the candidate factors. For each candidate number, you need to try all the candidate factors so you need the loops nested.
You will need to keep track of a sum.
You will need to know how to tell if a candidate factor is a factor. A candidate factor is a factor if the candidate number divided by the candidate factor has a remainder of 0. You can find the remainder of a division operation between integers using the C modulo operator (the % operator).
SPOILER ALERT !
I don't know of a fast way to find perfect numbers, I suspect no one does, because only 30 are known as of 1990 (http://mathforum.org/library/drmath/view/51516.html
) The only way I know is brute force. Brute force doesn't mean stupid, but the first attempt shown below will be stupid.
I will now drop the word "candidate". Everyone, even 2000 year old Greeks, knows that the first perfect number is 6, so we can start our search there.
# define END_NUMBER 50000
for(int number = 6; number < END_NUMBER; ++number)
int sum = 1; /* 1 is always a factor */
for (int factor = 2; factor < number - 1; ++factor)
if (number % factor == 0)
sum = sum + factor;
if (sum == number)
printf ("Yay, %d is perfect\n", number);
This attempt is stupid because it does more work than it needs to. On most newer computers, this will finish very quickly, but that is no reason to be lazy. There are 2 optimizations possible which are so obvious that even I thought of them. Also there is 1 cheat based on the assumption that all perfect numbers are even.
Try to optimize this. Be sure to let me know what you come up with.