# Thread: What is wrong with this code of perfect number generation

1. ## What is wrong with this code of perfect number generation

Hi, I wrote this simple code for perfect number printing.
A perfect number is one for which sum of its divisors is equal to the number itself like 1,6 etc
The code
prints initial 5 perfect numbers but when i seek 6th one which is 33550336, it just does not print anything but remain stuck at previous perfect no which is 8198.
I waited for hours but still nothing.
Any comment???

#include<stdio.h>
main()
{
long count,i,j,n,k;
long sum;
printf(" Enter how many perfect no to print\n");
scanf("%d", &n);
count=1;
sum=0;
printf("%d\t",1);
i=2;
while (count<=n-1)
{
sum = 0;
for (j=1;j<=i/2;j++)
{
k=i%j;
if(k==0)
sum=sum+j;
}
if (sum==i)
{
printf("%d\t",sum);
count = count +1;
}
i++;
}
}

2. What is this code that you speak of?

3. Code:
`while (count<=n-1)`

You never modify n after that line so no wonder it becomes an infinite loop.

4. Oh, you did post the code afterwards. Still, you need to format it properly, e.g.,
Code:
```#include<stdio.h>

int main(void)
{
long count, i, j, n, k;
long sum;
printf(" Enter how many perfect no to print\n");
scanf("%d", &n);
count = 1;
sum = 0;
printf("%d\t", 1);
i = 2;
while (count <= n - 1)
{
sum = 0;
for (j = 1; j <= i / 2; j++)
{
k = i % j;
if (k == 0)
sum = sum + j;
}
if (sum == i)
{
printf("%d\t", sum);
count = count + 1;
}
i++;
}
}```
I have taken the liberty of explicitly declaring the return type of main to be int.

Originally Posted by Shashank Mishra
when i seek 6th one which is 33550336, it just does not print anything but remain stuck at previous perfect no which is 8198.
I waited for hours but still nothing.
Larger composite numbers tend to have more divisors, and then you're testing more and more numbers, so it is probably just a case of more time being needed (or a faster algorithm, if feasible). You can always print some output every say, 10000 integers to convince yourself that your program is still running.

Originally Posted by MOS-6581
You never modify n after that line so no wonder it becomes an infinite loop.
No, it is not an infinite loop, assuming that there are enough perfect numbers to satisfy the request. Refer to:
Code:
`count = count + 1;`

5. Oh right I didn't notice that count was being modified. It's a bit hard to read the code without code tags. What is this code needed for anyway?

6. as laserlight said, it most probably due to the algorithm used, im sure google could shed some light on better algorithms to use if any(of course they are)

7. It is weird, I quickly tried the same algorithm with python (which is much slower), and I retrieved the result within a few seconds.

Are you working on embedded system or something ? Which compiler do you use ?

8. Originally Posted by HeavyZ
It is weird, I quickly tried the same algorithm with python (which is much slower), and I retrieved the result within a few seconds.
A result of 33550336 or of 8198? I ran a version of Shashank Mishra's program from post #1 (modified as prompted by compile warnings, along with my own "print some output every say, 10000 integers to convince yourself that your program is still running" suggestion), and for an input of 6, I certainly do not get the result "within a few seconds", and in fact even after a few minutes I am still getting my "10000 integer output", but not the expected output.

9. If I start testing with 33550300,

i = 33550300L;

it takes about 8 seconds for the output of 33550336.

And that's for only 37 numbers of that magnitude being tested.
Even starting at 10000000, there's over 23 million of them to test.

-

10. If you do the sums, with this approach, the time to find a given perfect value increases quadratically with that value.

So the time to get to 33550366 is about a million times the time needed to get to 8198.

BTW: 8198 is not a perfect number either.

11. Originally Posted by grumpy
BTW: 8198 is not a perfect number either.
It is just a typographical error: Shashank Mishra's program correctly finds 8128 as the fourth perfect number (though it incorrectly lists it as the fifth).

12. Originally Posted by laserlight
A result of 33550336 or of 8198? I ran a version of Shashank Mishra's program from post #1 (modified as prompted by compile warnings, along with my own "print some output every say, 10000 integers to convince yourself that your program is still running" suggestion), and for an input of 6, I certainly do not get the result "within a few seconds", and in fact even after a few minutes I am still getting my "10000 integer output", but not the expected output.
You're right, I started it with i = 33550336. This is of course faster, as grumpy explained.

13. This produced the first 5 numbers ( 6 28 496 8128 33550336 ) in about 25 minutes:

Code:
```#include<stdio.h>
#include <math.h>

int main(void)
{
long n, d1, d2, sum, limit;

for(n = 2; n <= 33550336L; n++)
{
limit = sqrt(n);

if(limit * limit == n)
{ 	sum = limit + 1;
limit = limit - 1;
}
else
sum = 1;

for(d1 = 2; d1 <= limit; d1++)
{	d2 = n / d1;
if (d1 * d2 == n)
sum = sum + d1 + d2;
}

if (sum == n)
printf("\n%d", sum);
}

printf("\n");
return 0;
}```
The test for "perfect" divisors only needs to range up to sqrt(n), instead of n/2.
For each perfect divisor found, (d1), another divisor exists: n/d1.
So the divisors are found in pairs, the first, d1, ranging from 2 to sqrt(n), and the second,
ranging from sqrt(n) to n/2.

Because the divisors are accumulated in pairs, an exception has to be made for a divisor of 1,
which would have a paired divisor equal to n. The sum should include 1, though. This is simply done
by including 1 in the initial value of sum, and starting the divisor test loop at 2.

An exception also has to be made for a perfect divisor equal to sqrt(n). It's pair is of the same
value and would therefor be summed in twice. This is handled simply by including sqrt(n) in the sum
initialization, and excluding it from the test range (limit-1).

-

14. Originally Posted by megafiddle
The test for "perfect" divisors only needs to range up to sqrt(n), instead of n/2.
For each perfect divisor found, (d1), another divisor exists: n/d1.
So the divisors are found in pairs, the first, d1, ranging from 2 to sqrt(n), and the second,
ranging from sqrt(n) to n/2.

Because the divisors are accumulated in pairs, an exception has to be made for a divisor of 1,
which would have a paired divisor equal to n. The sum should include 1, though. This is simply done
by including 1 in the initial value of sum, and starting the divisor test loop at 2.

An exception also has to be made for a perfect divisor equal to sqrt(n). It's pair is of the same
value and would therefor be summed in twice. This is handled simply by including sqrt(n) in the sum
initialization, and excluding it from the test range (limit-1).
Since you are going to be finding a pair of divisors on each iteration anyway, I think that actually calling the sqrt function is unnecessary, e.g.,
Code:
```#include <stdio.h>

#define N_THRESHOLD 33550336L

int main(void)
{
long n, d1, d2, sum;

for (n = 2; n <= N_THRESHOLD; n++)
{
/* Compute the sum of distinct positive divisors of n, excluding n: */
sum = 1;
for (d1 = 2;; d1++)
{
d2 = n / d1;
if (d1 >= d2)
{
break;
}
else if (d1 * d2 == n)
{
sum += d1 + d2;
}
}
/* Handle the case of n being a perfect square: */
if (d1 == d2 && d1 * d2 == n)
{
sum += d1;
}

/* Print n if n is a perfect number: */
if (sum == n)
{
printf("%ld\n", n);
}
}

return 0;
}```

15. Removing the sqrt() function is a nice improvement.

I am wondering if the sqrt function is guaranteed to return an integral value when the square root
is a perfect divisor, eg, 1000.00000000 returned as sqrt of 1000000.

It apparently worked in this case, but not sure if it always would.

-