Perfect Number

**loko** · 08-13-2005

I created a problem and solved it but i noticed that the outputting is kinda slow. Can someone here make a faster algo for this problem than mine pls?

This problem will output all perfect numbers between 1 and int max.

A perfect number is an integer that is equal to the sum of all of its factors other than itself..

e.g.
1 + 2 + 3 = 6

other perfect numbers are 28 and 496

PHP Code:


#include<stdio.h>

#include<conio.h>



int main()

{

    long num, ctr;

    long curtotal, max;

    clrscr();



    printf( "Input:" );

    scanf( "%ld", &max );

    printf( "\nOutput:\n\n" );



    for( num = 1; num < max; num++ ){

        for( ctr = 1, curtotal = 0; ctr < num; ctr++ ){

            if( ( num % ctr ) ==  0 )

                curtotal += ctr;

        }



        if( curtotal == num )

            printf( "%ld\n", num );

    }



    getch();

    return 0;

}

**Salem** · 08-13-2005

*shrug*
http://www.google.com/search?q=algor...erfect+numbers

**grumpy** · 08-13-2005

A way to speed things up would be to use an optimised method of finding prime factors of the number. All factors of a number can be computed by as the product of some of it's prime factors (raised to some power). Look up sieve of erastothenes for a method of computing primes.

**Rashakil Fol** · 08-13-2005

Or you could just write:

Code:

if (max >= 6) {
    puts("6");
    if (max >= 28) {
        puts("28");
        if (max >= 496) {
            puts("496");
            if (max >= 8128) {
                puts("8128");
                if (max >= 33550336) {
                    puts("33550336");
                }
            }
        }
    }
}

**quzah** · 08-13-2005

Use a lookup table. :P

Quzah.

**grumpy** · 08-13-2005

Originally Posted by Rashakil Fol

Or you could just write:

Code:

if (max >= 6) {
    puts("6");
    if (max >= 28) {
        puts("28");
        if (max >= 496) {
            puts("496");
            if (max >= 8128) {
                puts("8128");
                if (max >= 33550336) {
                    puts("33550336");
                }
            }
        }
    }
}

:-) Too bad this approach will not find any perfect number over 33550336 .....

**Rashakil Fol** · 08-13-2005

The 'long' datatype has an upper limit of 2147483647, in most situations, and no perfect numbers lie between 33550336 and 2147483647.

**moonlord** · 08-14-2005

hey, maybe the man wants to store the number in a list. then there would be prime numbers larger than 33550336.

anyway, erathostene wouldn't work for big numbers. you need an array of trunc(sqrt(x)) elements that can store atleast trunc(sqrt(x)), where x is the number to be tested.

**quzah** · 08-14-2005

hey, maybe the man wants to store the number in a list. then there would be prime numbers larger than 33550336.

If they want to store them in a list, then then they wouldn't be asking how to improve their alrogithm which uses longs, would they? It wouldn't really work to do comparisons as a long in hopes to improve on the speed of something which must be stored in a list due to it not fitting in a long, would it? Rhetorical.

Quzah.

**loko** · 08-14-2005

Originally Posted by Rashakil Fol

Or you could just write:

Code:

if (max >= 6) {
    puts("6");
    if (max >= 28) {
        puts("28");
        if (max >= 496) {
            puts("496");
            if (max >= 8128) {
                puts("8128");
                if (max >= 33550336) {
                    puts("33550336");
                }
            }
        }
    }
}

any better one? Cheating this bad is bad

**Prelude** · 08-14-2005

>Cheating this bad is bad
Cheating is good when not cheating means you write an inefficient algorithm to calculate something that you could more easily look up in a table.

**grumpy** · 08-15-2005

Originally Posted by moonlord

anyway, erathostene wouldn't work for big numbers. you need an array of trunc(sqrt(x)) elements that can store atleast trunc(sqrt(x)), where x is the number to be tested.

Sieve of Erastothenes works for large values. The challenges with finding large primes (or large perfect numbers) is representing integers that are greater than can be stored in basic types in C. And, no, it is not necessary to have an array of the order of sqrt(x) where x is the number being tested. All that is needed is to store the prime values themselves .... and the number of actual prime values <= x is substantially less than sqrt(x) for large x.

**moonlord** · 08-15-2005

Originally Posted by grumpy

Sieve of Erastothenes works for large values. The challenges with finding large primes (or large perfect numbers) is representing integers that are greater than can be stored in basic types in C. And, no, it is not necessary to have an array of the order of sqrt(x) where x is the number being tested. All that is needed is to store the prime values themselves .... and the number of actual prime values <= x is substantially less than sqrt(x) for large x.

right, i was mistaken. and what's the way of storage you think it's best? a list?

**grumpy** · 08-16-2005

Originally Posted by moonlord

right, i was mistaken. and what's the way of storage you think it's best? a list?

There are lots of possible ways (eg a list, an array that you dynamically resize, etc) of doing it. All ways involve some for of tradeoff between speed, memory usage, and a raft of other concerns.

The definition of "best" is highly subjective as it depends on which concerns are more important to you.

**moonlord** · 08-21-2005

well, i've remembered the math teacher told us smth about perfect numbers and checked my notebook:

Euler has proven that:
x = 2^n*(2^(n+1)-1) (natural n>0) and 2^(n+1)-1 is prime (Mersenne prime in fact) <=> x is a perfect number

hope this helps.

Thread: Perfect Number - faster Algo Pls..

Thread Tools

Search Thread

Display

Perfect Number - faster Algo Pls..

Similar Threads

Program giving errors

Number system base M, print numbers N digits wide...

Perfect Numbers - Need Help

Array of boolean