c - 查找从 2 到上限范围的所有友好数字对 - 不正确的输出

Question

我正在尝试编写一个函数来查找从 2 到给定上限的所有友好数字对。

我编写了一个函数来计算给定数字的除数之和。

我还编写了一个函数，它使用了以下事实:如果 num1 的除数之和为 S(num1)，并且 num2=s(num1)- num1 具有相同的除数和，则 num1 和 num2 是友好数。

这是我的代码:

#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;
}

但是，当我运行它时，我得到了错误的输出。例如，对于 upperRange 301，我得到 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 的 findSumOfDevisors() 有问题。也许其他代码也是如此。

1. sqrt() 没有义务给出一个完全正确的平方根 - 一些较弱的实现可能会导致一个值刚好高于或低于预期答案.结合截断分数的 (int)，像 123.999999999... 这样的答案变成 123 而不是 124。无论如何，这里不需要 float 学及其精度问题。

   建议只使用整数数学:

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

2. 避免溢出。

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

3. 对同一个值求和两次？当除数和商相同时，代码会将它们都计算在内。我希望只有一个。

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

4. 为了完整起见，我希望 findSumOfDevisors(0)、findSumOfDevisors(1) 像 OP 的代码一样返回 0 而不是 1。负数是另一个 Unresolved 问题。

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

5. 使用昂贵的 /, % 还是买二送一？考虑以下代码。 % 和 / 都可能调用一些昂贵的余数和除法计算。然而，对于许多优秀的编译器，num/i 和 num % i 将导致发出的代码在一个操作中计算这两个值。最好为了清晰起见而编写代码，但如果持久性是一个问题，请调查一个好的优化编译器的结果。

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