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

  1. #1
    Registered User
    Join Date
    May 2014
    Posts
    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. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,744
    What is this code that you speak of?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2014
    Posts
    121
    Code:
    while (count<=n-1)

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

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,744
    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.

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

    Quote 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;
    Last edited by laserlight; 05-27-2014 at 01:45 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    May 2014
    Posts
    121
    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. #6
    Registered User
    Join Date
    Nov 2012
    Posts
    157
    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. #7
    Registered User
    Join Date
    May 2014
    Posts
    3
    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. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,744
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Mar 2011
    Posts
    596
    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. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,744
    Quote 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).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    May 2014
    Posts
    3
    Quote Originally Posted by laserlight View Post
    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. #13
    Registered User
    Join Date
    Mar 2011
    Posts
    596
    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).

    -
    Last edited by megafiddle; 05-31-2014 at 05:52 PM.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,744
    Quote 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;
    }
    Last edited by laserlight; 06-01-2014 at 05:06 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Mar 2011
    Posts
    596
    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.

    -

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. perfect number
    By mallyg34 in forum C++ Programming
    Replies: 9
    Last Post: 04-03-2010, 02:20 PM
  2. Replies: 5
    Last Post: 10-05-2009, 10:21 AM
  3. What is perfect number
    By IPCHU in forum C Programming
    Replies: 5
    Last Post: 12-08-2006, 11:23 AM
  4. Perfect number...
    By Argo_Jeude in forum C++ Programming
    Replies: 8
    Last Post: 07-12-2005, 01:53 PM
  5. Perfect number
    By TheSki in forum C++ Programming
    Replies: 2
    Last Post: 10-30-2001, 04:34 PM

Tags for this Thread