CODEWITHSUNDEEP
mathnumber-theoryperfect-numbers
Shah Shishir
Shah Shishir

Reputation: 191

How to find perfect numbers upto 10^18 in C?

I have a C code off finding large perfect numbers below,

#include <stdio.h>

int main ()
{
    unsigned long long num,i,sum;

    while (scanf ("%llu",&num) != EOF && num)
    {
        sum = 1;

        for (i=2; i*i<=num; i++)
        {
            if (num % i == 0)
            {
                if (i*i == num)
                    sum += i;
                else
                    sum += (i + num/i);
            }
        }

        if (sum == num)
            printf ("Perfect\n");
        else if (sum > num)
            printf ("Abundant\n");
        else
            printf ("Deficient\n");
    }

    return 0;
}

I tried to find whether a number is perfect, abundant or deficient. I run a loop upto the square root of numto minimize the runtime. It works fine <= 10^15 but for the larger values it takes too long time to execute.

For example,for the following input sets,

8
6
18
1000000
1000000000000000
0

this code shows the following outputs,

Deficient
Perfect
Abundant
Abundant
Abundant

But, for 10^16 it doesn't respond quickly.

So, is there any better way to find a perfect number for too long values? Or is there any better algorithm to implement here??? :)

Upvotes: 0

Views: 1012

Answers (3)

HiddenHopes
HiddenHopes

Reputation: 63

// Program to determine whether perfect or not

# include <bits/stdc++.h>
using namespace std;

map<long long int, int> mp;    // to store prime factors and there frequency

void primeFactors(long long int n)
{
// counting the number of 2s that divide n
while (n%2 == 0)
{
    mp[2] = mp[2]+1;
    n = n/2;
}

long long int root = sqrt(n);
// n must be odd at this point.  So we can skip every even numbers next
for (long long int i = 3; i <= root; i = i+2)
{
    // While i divides n, count frequency of i prime factor and divide n
    while (n%i == 0)
    {
        mp[i] = mp[i]+1;
        n = n/i;
    }
}

// This condition is to handle the case whien n is a prime number
    // greater than 2
    if (n > 2)
    {
        mp[n] = mp[n]+1;
    }
}

long long int pow(long long int base, long long int exp)
{
    long long int result = 1;
    base = base;
    while (exp>0)
    {
        if (exp & 1)
            result = (result*base);
        exp >>= 1;
        base = (base*base);
    }
    return result;
}

int main ()
{
    long long num, p, a, sum;

    while (scanf ("%lld",&num) != EOF && num)
    {
        primeFactors(num);
        sum = 1;

        map<long long int, int> :: iterator i;
        for(i=mp.begin(); i!=mp.end(); i++)
        {
            p = i->first;
            a = i->second;
            sum = sum*((pow(p,a+1)-1)/(p-1));
        }

        if (sum == 2*num)
            printf ("Perfect\n");
        else if (sum > num)
            printf ("Abundant\n");
        else
            printf ("Deficient\n");

        mp.clear();
    }

    return 0;
}

Upvotes: 1

Rory Daulton
Rory Daulton

Reputation: 22564

Yes, there is a better algorithm.

Your algorithm is basically the simple one--adding up the divisors of a number to find... the sum of the divisors of a number (excluding itself). But you can use the number-theoretic formula for finding the sum of the divisors of a number (including itself). If the prime numbers dividing n are p1, p2, ..., pk and the powers of those primes in the canonical decomposition of n are a1, a2, ..., ak, then the sum of the divisors of n is

(p1**(a1+1) - 1) / (p1 - 1) * (p2**(a2+1) - 1) / (p2 - 1) * ...
    * (pk**(ak+1) - 1) / (pk - 1)

You can find the prime divisors and their exponents more quickly than finding all the divisors of n. Subtract n from that expression above and you get the sum you want.

There are some tricks, of course, to find the pis and ais more efficiently: I'll leave that to you.

By the way, if your purpose is just to find the perfect numbers, as in your title, you would do better to use Euclid's formula for even prime numbers. Find the Mersenne prime numbers by examining all 2**p-1 for prime p to see if they are prime--there are shortcuts to doing this as well--then constructing a perfect number from that Mersenne prime. This would leave out any odd perfect numbers, though. If you find any, let the mathematical community know--that would make you world famous.

Of course, the fastest way of all to find perfect numbers is to use the lists already made of some of them.

Upvotes: 2

DevilaN
DevilaN

Reputation: 1474

It is a matter of factorization of numbers. You can read more here: https://en.wikipedia.org/wiki/Integer_factorization

Unfortunately no good news for you - the bigger the number gets, the longer it takes.

To start with your code, try not to multiply i*i each iteration. Instead of: for (i=2; i*i<=num; i++)

calculate square root of num first, and then compare i <= square_root_of_num in the loop.

Upvotes: 1

Related Questions