c - 我如何列出 0 和 n 之间的数字，其中数字与其正因子之和将构成一个完美的平方？

Question

我应该将 n 作为用户的输入，并在特定条件下列出 0 到 n 之间的一些数字。

条件是这样的:数字和它的所有除数的总和应该提供一个完美的平方。 (例如:假设 a 的约数是 b 和 c。a + b + c 应该是一个完美的平方)

另外，作为输出，我必须列出:

数 - 它的所有除数按升序排列 - 除数之和(a b c b+c)

作为一个完整的例子，如果 'n' 是 50，那么它应该打印(因为 33 是​​唯一提供小于 50 的条件的数字):33 1 3 11 33 48

到目前为止，我已经编写了一个函数来检查一个数字是否是一个完美的正方形。另外，我也曾尝试编写一个可以完成所有这些的函数，但没有成功。那么，通过查看代码，您能告诉我哪里出了问题吗？我应该怎么做？

#include <stdio.h>
#include <stdbool.h>

int squareRoot(int n)
{
    int a= 0;

    for(; a*a <=n; a= a+1 )
        ;

    return a-1;
}

int IsPerfectSquare(int num)
{
    int b;

    b = squareRoot(num);

    if (b*b == num)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main()
{
    int n0, n1, n2, n3, sum, n4, n5;

    scanf("%d", &n0);

    for(n1 = 0 ; n1<n0; n1++)
    {
        sum = 0;
        for(n2 = n1 ; n2 <= n1 && n2 >0 ;n2--)
        {
          if (n1%n2 == 0) 
          {
            n3 = n1/n2;
            sum = sum + n3;
            n4 = sum + n1;
            n5 = IsPerfectSquare(n4);
            if (n5 == 1)
            {   
             printf("%d %d %d", n1, n3, sum);
            }
          }
        }
    }       
}

Answer 1

使用评论中所述的指南，并通过两次因素分析避免数组，我最终得到:

#include <stdio.h>
#include <stdbool.h>

static int squareRoot(int n)
{
    int a;

    for (a = 0; a * a <= n; a++)
        ;

    return a - 1;
}

static bool IsPerfectSquare(int num)
{
    int b;

    b = squareRoot(num);

    if (b * b == num)
        return true;
    else
        return false;
}

int main(void)
{
    int n0;

    if (scanf("%d", &n0) != 1)
    {
        fprintf(stderr, "Failed to read an integer\n");
        return 1;
    }

    for (int n1 = 1; n1 < n0; n1++)
    {
        int sum = n1 + 1;
        for (int n2 = 2; n2 <= n1 / 2; n2++)
        {
            if (n1 % n2 == 0)
                sum += n2;
        }
        if (IsPerfectSquare(sum + n1))
        {
            printf("%d 1", n1);
            for (int n2 = 2; n2 <= n1 / 2; n2++)
            {
                if (n1 % n2 == 0)
                    printf(" %d", n2);
            }
            printf(" %d %d\n", n1, sum);
        }
    }
    return 0;
}

运行时(使用 Bash here string 提供输入和自定义(自制)计时命令(-m 表示毫秒)，我得到了输出:

$ timecmd -m -- fs17 <<< '1000' 
2019-10-23 00:07:43.032 [PID 9520] fs17
33 1 3 11 33 48
90 1 2 3 5 6 9 10 15 18 30 45 90 234
385 1 5 7 11 35 55 77 385 576
420 1 2 3 4 5 6 7 10 12 14 15 20 21 28 30 35 42 60 70 84 105 140 210 420 1344
649 1 11 59 649 720
900 1 2 3 4 5 6 9 10 12 15 18 20 25 30 36 45 50 60 75 90 100 150 180 225 300 450 900 2821
2019-10-23 00:07:43.046 [PID 9520; status 0x0000]  -  0.013s
$

如评论中所述，达到 1,000,000 需要更长的时间。