2
\$\begingroup\$

A number is perfect if it is equal to the sum of all its divisors. For example divisors of 6 are 1, 2, 3. I want to read numbers, and for each number to print 1 if it is perfect and 0 if it's not perfect. Numbers are smaller than 10 ^ 19. How would I do it faster? My version:

#include <stdio.h>
#include <stdlib.h>
double perfectCheck( double number )
{
    double i, sum = 0;
    for( i = 1; i <= number / 2; i++ )
        if(( int )( number / i ) * i == number )
            sum += i;
    return sum;
}

int main()
{
    double n, i, m;
    scanf( "%lf", &n );
    for( i = 0; i < n; i++ )
    {
        scanf( "%lf", &m );
        if( perfectCheck( m ) == m )
            printf( "1 " );
        else
            printf( "0 " );
    }
    return 0;
}

Input:

5
28 7 8 9 6

Output:

1 0 0 0 1

I use C89.

\$\endgroup\$
4
\$\begingroup\$

Finding divisors faster

Instead of checking all numbers until number / 2, it's enough to search until sqrt(number), and count the divisor pairs. For example, in the case of 6, initialize sum = 1, because 1 will be always part of the sum, and then when you see 2, also add 6 / 2 to the sum. (You can get sqrt with #include "math.h".) Also, you can break out of the loop when sum exceeds the target value.

There is one more important point that can slow your implementation down, is that all the variables are double instead of int. This is not only unnatural for the given task, floating point math is expensive in general. So simply rewriting the program so that number, i, m, n are all integers, will make a big difference.

Make perfectCheck return boolean

Currently perfectCheck returns the sum of divisors. You could make it return a bool:

return sum == number;

You can get the bool type in C99+ with #include "stdbool.h".

And then you can write the main function a bit simpler:

for (i = 0; i < n; i++)
{
    scanf("%d", &m);
    printf("%d ", perfectCheck(m));
}
\$\endgroup\$
3
\$\begingroup\$

Well, if you want to find all divisors, consider factorizing the number and then enumerating combinations of individual factors.

The more factors a number has, the more time doing so saves.


  1. I'm missing your includes. No, really.

  2. Avoid floating-point arithmetic where you can. unsigned long long can deal with at least 264-1, which is more than 1019.
    double would lose precision before then.

  3. Never assume getting input succeeds.

  4. perfectCheck's return is curious. Why the sum, instead of the result of the comparison, preferably as a bool from C99 <stdbool.h> (or an int without)?

  5. Anyway, perfectCheck is not a good name for a function, being a noun. isPerfect would be better, and reinforces that the return should change.

\$\endgroup\$
  • \$\begingroup\$ I do not understand what do you mean by "factorizing the number and then enumerating combinations of individual factors". Do I have to find all prime factors? How to enumerate the combinations? I am not a native English speaker, but I found this dictionary.cambridge.org/dictionary/english/… translation for enumerate. \$\endgroup\$ – Timʘtei Jun 4 '17 at 4:38
  • \$\begingroup\$ Yes, factorize = find the prime factors, and enumerating the combinations to find the divisors. \$\endgroup\$ – Deduplicator Jun 4 '17 at 11:39
  • \$\begingroup\$ I tried to use long, but I am using codeblocks on Windows 7 ultimate 64 bit and codeblocks is a 32 bit compiler or I do not know how to set it to 64 bit version. I have to store numbers in double which makes the code slower. What to do in this situation? \$\endgroup\$ – Timʘtei Jun 4 '17 at 12:30
  • \$\begingroup\$ Sorry, gave the wrong type. You need C99 unsigned long long or such. double is not only slow, but also wrong. \$\endgroup\$ – Deduplicator Jun 4 '17 at 13:13
0
\$\begingroup\$

The reason why I answer my question is that each of the other answers were helpful, but no one really solved my problem. After I considered the other answers and made some more research I wrote the next code which is as fast as I needed.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int isPerfect( long number )
{
    long i, sum = 1;
    int y = 1;
    if( number % 2 ) y = 2;
    for( i = 2; i <= sqrt( number ); i += y )
        if( number % i == 0 )
            sum = sum + i + number / i;
    return sum == number;
}

int main()
{
    long m;
    int n;
    int i;
    scanf( "%d", &n );
    for( i = 0; i < n; i++ )
    {
        scanf( "%ld", &m );
        if( m == 1 )
            printf( "0 " );
        else printf( "%d ", isPerfect( m ));
    }
    return 0;
}

What made the biggest difference was skipping even numbers for odd input. It is working only on a 64 bit compiler.

\$\endgroup\$
0
\$\begingroup\$

All known perfect numbers are of the form \$2^k \cdot (2^{k+1} - 1)\$ where \$(2^{k+1} - 1)\$ is prime (example source). So a faster check is if the number is of that form and then check the primality. This is because the check for that form is faster than summing the factors. The primality check is roughly the same speed as summing the factors, but we only have to do that if it is of the proper form.

int isPrime(long long number)
{
    long i;
    long increment = 4;

    if (number % 2 == 0 && number > 2) {
        return 0;
    }

    if (number % 3 == 0 && number > 3) {
        return 0;
    }

    for (i = 5; i <= number / i; i += increment) {
        if (number % i == 0) {
            return 0;
        }

        increment = 6 - increment;
    }

    return 1;
}

int isPerfect( long long number )
{
    long long m = 2;
    while (number % m == 0)
    {
        m *= 2;
    }

    return (m - 1) * m / 2 == number && isPrime(m - 1);
}

int main()
{
    long long n, m;

    scanf( "%ld", &n );
    for( ; 0 < n; n-- )
    {
        scanf( "%ld", &m );
        printf( "%d ", isPerfect( m ) );
    }
}

I'm not going to justify my isPrime function here. Check this answer if you really want to know how it works.

The m variable equals \$2^{k+1}\$ in the previous formula, so m/2 is \$2^k\$ and m-1 is \$(2^{k+1} - 1)\$. Thank you, Euclid and Euler.

Another alternative would be to generate all the perfect numbers first. There are fewer than 64 of them in the 64 bit range. Then just check if the scanned number is one of the perfect numbers.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.