Perfect number calculator, how to increase speed

[lambolighting]

Hello everyone, i have a program which calculates and finds perfect numbers. I want to make it faster but i can't seem to find a way.

I've modified it a bit temporalily in order to see which number it checks at the moment and know how far and how fast it has reached. Here's my code:

/*
Perfect Numbers
show perfect numbers from 1-endnum
*/

#include <iostream>

using namespace std;

int main(void)
{
    //variables
    long int i,j,sumOfFactors,endnum;

    cout << "Check from 1 up to which number?" << endl;
    cin >> endnum;
    //check numbers from 1-endnum
    for (i = 1; i <= endnum; i++)
        {
            sumOfFactors = 0;
            cout << "Checking: " << i << endl;
            //look for the factors of a number
            for (j = 1; j < i; j++)
                {
                    //check for factors and add them up
                    if (0 == (i % j))
                        {
                            sumOfFactors += j;
                        }
                }
        }
    getchar();
    return 0;
}

Any help would be appreciated!

[PBachmann]

You can set sumOfFactors equal to 1, and have the for loop that checks for factors start at 2.
The other suggestion I have is to start checking at i=6 and increment by 2 since odd perfect numbers haven't been discovered yet.

[lambolighting]

So the code now looks like this, it surely has increased a lot!
I hope that i can get some more suggestions, looks like it will never reach 33550336 which is the next one.

/*
Perfect Numbers
show perfect numbers from 1-endnum
*/

#include <iostream>

using namespace std;

int main(void)
{
    //variables
    long int i,j,sumOfFactors,endnum;

    cout << "Check from 1 up to which number?" << endl;
    cin >> endnum;
    //check numbers from 1-endnum
    for (i = 6; i <= endnum; i += 2)
        {
            sumOfFactors = 1;
            cout << "Checking: " << i << endl;
            //look for the factors of a number
            for (j = 2; j < i; j++)
                {
                    //check for factors and add them up
                    if (0 == (i % j))
                        {
                            sumOfFactors += j;
                        }
                }
        }
    getchar();
    return 0;
}

EDIT:
On second thought although this improves the speed by A LOT i want to count them one by one in order to be more precise (as if we don't know that odd perfect numbers haven't been found).

[Duthomhas]

A couple of thoughts:

/s/main(void)/main()/

You should add a check after line 16 (and before 17) that validates !(endnum < 6), since any such number cannot be perfect.

You can ignore looking for odd perfect numbers. They may exist, but not anywhere within the range of values your program can access.

Hope this helps.

[Duthomhas]

By the way, the reason your program is so slow is that it does two things:

    1. Brute forces all possible perfect numbers
    2. Brute forces all possible divisors

The divisors problem can be fixed by only checking divisors ≤ √(endnum).
If a divisor is found, add both it and the quotient to the sum (being careful to avoid adding √(endnum) twice -- though that won't matter for your range of values).


There is another way to solve this, but it involves a bit more code (which may be significant for you).

All (known) perfect numbers are of the form:

    2^n-1 × (2ⁿ-1)

You just need, then, a function to factorize endnum. After that you only need to check:

    (final factor + 1) is a power of 2
    (final factor + 1) == 2^{(number of factors)}

This produces a significant savings in time.
But, it is a lot more programming, using multiple functions...


So, try the sqrt() trick (#include <cmath>) first and see if that doesn't cut times down enough for you.

Hope this helps.