PDA

View Full Version : List Perfect Numbers(C++)



navneeth
July 11th, 2007, 03:43 PM
This is an utterly simple program, but for some reason unknown to me, this does not work properly.



//This program lists all the perfect numbers less than a given positive integer(user input)

#include<iostream>

using namespace std;

main()
{

int n,m,i,sum=1;

cout << "List all the perfect numbers less than: ";
cin >> m;

for(n=2;n<m;n++)
{
for(i=n-1;i>1;i--)
{
if(n%i == 0)
sum += i;
}

if(sum == n)
cout << n <<endl;
}

}


I use the GNU g++ compiler v4.1.2. It compiles fine, but when I execute and give the input, I get the back shell prompt. I must add that the second for loop works(i.e., when I test if a given number is perfect or not, or in other words, a fixed n), but that's not what I want here.

Thanks for any help.

GeneralZod
July 11th, 2007, 03:56 PM
Is m being read in correctly? Should "sum" not be reset to 1 for each n?

rodo->dave
July 11th, 2007, 04:57 PM
here is mine:



//This program lists all the perfect numbers less than a given positive integer(user input)

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

int main (int argc, char **argv)
{
int n;
int max;
int output;

if (argc < 2) {
printf("usage: %s number\n", argv[0]);
return(-1);
}

max = atoi(argv[1]);

// using the formula 2^n-1 (2^n -1)
for (n = 2; n < max; n++) {
output = pow(2, n-1);
output *= (pow(2, n) - 1);

printf("%d\n", output);
}
}


Not exactly what you want but output gives
$ perfect_num 10
6
28
120
496
2016
8128
32640
130816
$

I got the formula here:
http://en.wikipedia.org/wiki/Perfect_number

navneeth
July 11th, 2007, 06:14 PM
Is m being read in correctly? Should "sum" not be reset to 1 for each n?

Exactly. Thank you. :)

vexorian
July 11th, 2007, 06:23 PM
I just felt the urge to request you to use the O(sqrt(n)) solution... ... sorry.



//This program lists all the perfect numbers less than a given positive integer(user input)

#include<iostream>
#include<cmath>

using namespace std;

main()
{

int n,m,i,sum=1;

cout << "List all the perfect numbers less than: ";
cin >> m;

for(n=2;n<m;n++)
{
sum=1;
int q=sqrt(p);

for(i=2;i<=q;i++)
{
if(n%i == 0)
{
sum += n/i + i;
if(sum>n) break;
}
}

if(sum == n)
cout << n <<endl;
}

}

hod139
July 11th, 2007, 06:48 PM
here is mine:

<snip>
Not exactly what you want but output gives
$ perfect_num 10
6
28
120
496
2016
8128
32640
130816
$

I got the formula here:
http://en.wikipedia.org/wiki/Perfect_number

This code is wrong. The first 4 perfect numbers are:
6
28
496
8128

You misunderstood the formula provided by wikipedia. All perfect numbers have the form: 2^(n−1)(2^n − 1), however, not all 2^(n−1)(2^n − 1) are perfect numbers. Only when 2^n − 1 is prime, is the number a perfect number. Values of n for which 2^n − 1 is prime are known as Mersenne primes. (http://en.wikipedia.org/wiki/Mersenne_prime)

rodo->dave
July 11th, 2007, 06:57 PM
This code is wrong. The first 4 perfect numbers are:
6
28
496
8128

You misunderstood the formula provided by wikipedia. All perfect numbers have the form: 2^(n−1)(2^n − 1), however, not all 2^(n−1)(2^n − 1) are perfect numbers. Only when 2^n − 1 is prime, is the number a perfect number. Values of n for which 2^n − 1 is prime are known as Mersenne primes. (http://en.wikipedia.org/wiki/Mersenne_prime)

Yes, you are correct; in the time between posts I looked at the wiki article more closely and I changed my code only do the calc if the number was prime.. .which I believe is correct now:

$ perfect_num 12
6
28
496
8128
2096128
$

And Just in case anybody cares:


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

int is_prime(int d);


int main (int argc, char **argv)
{
int n;
int max;
double output;

if (argc < 2) {
printf("usage: %s number\n", argv[0]);
return(-1);
}

max = atoi(argv[1]);

// using the formula 2^n-1 (2^n -1)
for (n = 2; n < max; n++) {
if (is_prime(n)) {
output = pow(2, n-1);
output *= (pow(2, n) - 1);

printf("%.0f\n", output);
}
}

return(0);
}

int is_prime(int d)
{
int is_prime = 1;
int n;


for (n = 2; n < d; n++) {
if ((d % n) == 0) {
is_prime = 0;
break;
}
}

return(is_prime);
}

Thanks! Enjoyed the topic (so far).. I had never done anything with 'perfect numbers' before so this is my first exposure.

rodo->dave
July 11th, 2007, 07:22 PM
Well, it appears that my fifth 'perfect number' is not perfect afterall :(
should be 33550336

solution: check if "(pow(2, n) - 1)" is prime :)

output is now:
$ perfect_num 18
6
28
496
8128
33550336
8589869056
$

which agrees with the article

hod139
July 11th, 2007, 09:47 PM
I modified your isPrime test, which doesn't seem correct. In fact, we are looking for Mersenne primes and there are only 44 known, so it is easiest to simply build a lookup table. The modified code is below.



#include <cstdio>
#include <cmath>
#include <map>

// global map of known mersenne primes
std::map<int, bool> knownMersennePrimes;

// this is only first 10 of known 44
void initMap(){
knownMersennePrimes[2] = true;
knownMersennePrimes[3] = true;
knownMersennePrimes[5] = true;
knownMersennePrimes[7] = true;
knownMersennePrimes[13] = true;
knownMersennePrimes[17] = true;
knownMersennePrimes[19] = true;
knownMersennePrimes[31] = true;
knownMersennePrimes[61] = true;
knownMersennePrimes[89] = true;
}

bool isMersennePrime(int d)
{
return knownMersennePrimes[d];
}

int main (int argc, char **argv)
{
if (argc < 2) {
printf("usage: %s number\n", argv[0]);
return(-1);
}

int max = atoi(argv[1]);

// create the map of known mersenne primes
initMap();

// using the formula 2^n-1 (2^n -1)
double output;
for (int n = 2; n < max; ++n) {
if (isMersennePrime(n)) {
output = pow(2, n-1);
output *= (pow(2, n) - 1);

printf("%.0f\n", output);
}
}

return(0);
}
Now, running


perfect_num 90
produces:


6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128
2658455991569831745807614120560689152
19156194260823610729479337839378864795234239027295 0272
The reported number of perfect numbers is correct at 10, however the last two are not correct since we overflowed the double value. They are close though. The last two should have been:
2658455991569831744654692615953842176, and

19156194260823610729479337808430363813099732154816 9216

Edit: I turned your code into C++ so I could use the std::map

rodo->dave
July 11th, 2007, 11:51 PM
cool. Good job!