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

What is this code that you speak of?

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;

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.

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.

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).

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).

-

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;
}