Finding all pairs of amicable numbers from 2 to an upper range - incorrect output

Question

I am trying to write a function which finds all pairs of amicable numbers from 2 to a given upper range.

I wrote a function that finds the sum of divisors of a given number.

I also wrote a function that uses the fact that if sum of devisors of num1 is S(num1), and num2=s(num1)-num1 has the same sum of devisors, then num1 and num2 are amicable numbers.

Here is my code:

#define _CRT_SECURE_NO_WARNINGS

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

void amicableNumbers(int n);
int findSumOfDevisors(int num);

void main() {
    int upperRange;

    printf("enter the value for upper range: ");
    scanf("%d", &upperRange);
    printf("the amicable numbers between 2 and %d:\n", upperRange);
    amicableNumbers(upperRange);
}

void amicableNumbers(int n) {
    int sum, sum2, i;

    for (i = 2; i <= n; i++) {
        sum = findSumOfDevisors(i);
        if (sum > i && sum <= n) {
            sum2 = findSumOfDevisors(sum);
            if (sum2 == i)
                printf("%d and %d \n", i, sum);
        }
    }
}

int findSumOfDevisors(int num) {
    int sum = 1, i, n;
    
    n = (int)sqrt((double)num);
    for (i = 2; i <= n; i++) {
        if ((n % i) == 0) {
            sum += i;
            sum += n / i;
        }
    }
    return sum;
}

However, when I run this I get the wrong output. For instance, for the upperRange 301, I get that there are not any amicable numbers in the range 2-301.

Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. For instance, the pair 220 and 284 are amicable numbers. The sum of the proper divisors of 220 is 1+2+4+5+10+11+20+22+44+55+110=284 and the sum of the proper divisors of 284 is 1+2+4+71+142=220.

A proper divisor to a number is a positive factor to that number except the number itself.

Answer 1

OP's findSumOfDevisors() has troubles. Perhaps other code does too.

1. sqrt() is not obliged to give an exactly correct square root - some weaker implementations may result in a value just above or just below the expected answer. Coupled with the (int) which truncates the fraction, an answer like 123.999999999... becomes 123 instead of 124. In any case, floating point math with its precision issues is not needed here.

   Suggest only using integer math:

   // n =(int) sqrt((double)num);
   // for (i = 2; i <= n; i++)
   for (i = 2; i <= num/i; i++)
   

2. Avoid overflow.

   // for (i = 2; i*i <= num; i++)  `i*i` may overflow.
   for (i = 2; i <= num/i; i++)
   

3. Summing the same value twice? When the divisor and quotient are the same, code counts them both. I'd expect only one.

   sum += i;
   // sum += n / i;
   if (i != n/i) sum += n/i;
   

4. For completeness, I'd expect findSumOfDevisors(0), findSumOfDevisors(1) to return 0 and not 1 like OP's code. Negative numbers are another issue not addressed.

   // int sum = 1;
   int sum = num > 1;
   

5. Using expensive /, % or getting 2-for-1? Consider the following code. The % and / each invoke potentially some an expensive remainder and division calculation. Yet with many good compilers, the num/i and num % i will cause emitted code to calculate both of those in one operation. Best to code for clarity, yet if permanence is a concern, investigate the result of a good optimizing compiler.

   for (i = 2; i < num/i; i++) {
     if (num%i == 0) {
   

Answer 2

It is not advisable to use floating point arithmetic in findSumOfDivisors, try this instead:

int findSumOfDivisors(int num) {
    int sum = 1, div, i;

    for (i = 2; i <= (div = num / i); i++) {
        if (num % i == 0) {
            sum += i;
            if (i == div)
                break;
            sum += div;
        }
    }
    return sum;
}

Furthermore, your amicableNumbers function is too complicated, you should simply test if the sum of divisors of the sum is the original number:

void amicableNumbers(int n) {
    int sum, i;

    for (i = 2; i <= n; i++) {
        sum = findSumOfDivisors(i);
        if (sum > i && sum <= n && findSumOfDivisors(sum) == i)
            printf("%d and %d\n", i, sum);
        }
    }
}

Finally, the prototype for main without arguments is int main(void) and you should test the return value of scanf() and return 0 from main.

Here is an improved version:

#include <stdio.h>

int findSumOfDivisors(int num) {
    int sum = 1, div, i;

    for (i = 2; i <= (div = num / i); i++) {
        if (num % i == 0) {
            sum += i;
            if (i == div)
                break;
            sum += div;
        }
    }
    return sum;
}

void amicableNumbers(int n) {
    int sum, i;

    for (i = 2; i <= n; i++) {
        sum = findSumOfDivisors(i);
        if (sum > i && sum <= n && findSumOfDivisors(sum) == i)
            printf("%d and %d\n", i, sum);
        }
    }
}

int main(void) {
    int upperRange;

    printf("enter the value for upper range: ");
    if (scanf("%d", &upperRange) == 1) {
        printf("the amicable numbers between 2 and %d:\n", upperRange);
        amicableNumbers(upperRange);
    }
    return 0;
}

Answer 3

Your findSumOfDevisors function is wrong. Besides, IMO sqrt() function is overwhelming for performance. Instead, you should use i <= num / 2

int findSumOfDevisors(int num)
{
    int sum = 1, i,n;

    //n =(int) sqrt((double)num);
    for (i = 2; i <= num / 2; i++)
    {
        if ((num % i) == 0)
        {
            sum += i;
        }
    }
    return sum;
}

Moreover, if (sum > i && sum <= n) can be simplified as i < sum

Answer 4

the problem is in this function

int findSumOfDevisors(int num)

It's a typing mistake you wanted to put num not n the correct function is

int findSumOfDevisors(int num)
{
int sum = 1, i,n;

 n =(int) sqrt((double)num);
for (i = 2; i <= n; i++)
{
    if ((num % i) == 0)
    {
        sum += i;

        // If divisors are equal, add only one 
        if (num /i != i)
        {
            sum += num / i;
        } 
    }
}
return sum;
}