user3594736 user3594736 - 3 months ago 54
C Question

C - Find all amicable numbers between limits

First a definition: An amicable pair of numbers consists of two different integers where the
sum of the divisors of the first integer is equal to the second integer, and the
sum of the divisors of the second integer is equal to the first integer. A perfect number is a number that equals the sum of its own divisors.

What I want to do is make a program that asks the user for a lower limit, and an upper limit and then presents him/her with all the amicable pairs (one per line) between those two limits. If there's a perfect number only one number needs to be printed (not a pair in its case).

The whole idea is pretty confusing to me, so I'm looking for some assistance.

Here's what I have to start with, I know that sumDivisors() should be more or less correct, but main() is merely checking if the two inputted numbers are amicable or not - might have to do a complete overhaul of this since I want all the pairs between two given limits.

long sumDivisors(long a)
{
long s=0,i;
for(i=1;i<=a/2;i++)
{
if(a%i==0)
{
s+=i;
}
}
return s;
}


int main()
{
long t,n,s1;
scanf("%ld",&t);
while(t--)
{
scanf("%ld",&n);
s1=sumDivisors(n);
if(n==sumDivisors(s1))
{
printf("Yes\n");
}
else printf("No\n");
}
return 0;
}

Answer

You could write main() like this:

int main ()
{
    // assumes 1 <= min <= max
    long min = 1;
    long max = 10000;
    long n = max - min + 1;
    long * s = malloc (sizeof(long) * n);
    long i, j;

    for (i = min; i <= max; i++) {
        s[i - min] = sumDivisors (i);
    }

    // search for perfect numbers
    for (i = min; i <= max; i++) {
        if (s[i - min] == i) {
            printf ("perfect number:\t%ld\n", i);
        }
    }

    // search for amicable pairs
    for (i = min; i <= max; i++) {
        for (j = i + 1; j <= max; j++) {
            if ((s[i - min] == j) && (s[j - min] == i)) {
                printf ("amicable pair:\t(%ld, %ld)\n", i, j);
            }
        }
    }

    free (s);
    return 0;
}

I chose to precompute the sum of divisors for each number in the range. Then to find perfect numbers you just check them in sequence. Likewise to find amicable pairs you just check each pair in sequence. It is not efficient but it gets the job done.

Comments