获取将数字表示为两个整数乘积的所有方法

Question

我最近一直在寻找数字的约数，并决定尝试编写一个程序，打印出所有将数字 N 表示为两个整数乘积的方法。我写了一个对正数起作用的并且只考虑正数来构成乘积。

#include <iostream>
#include <cmath>

int main()
{
    int n;
    std::cin >> n;

    int root = std::sqrt(n);
    for(int i = 1; i <= root; i++)
    {
        if(n % i != 0)
            continue;

        int j = n / i;  
        std::cout << i << ", " << j << std::endl;
    }

    return 0;
}

上面的代码只是找到 N 的所有约数并将它们成对打印出来。它工作正常，但我想尝试让它找到所有可能的方法到达 N，而不仅仅是正数。

比如我在上面的程序中输入10，结果就是(1, 10), (2, 5)；这些是正确的，但是还有其他方法可以将两个数字相乘并得到 10。它涉及负数：(-1, -10), (-2, -5) 也是解决方案，因为当您将两个负数相乘时，你最终得到了一个积极的结果。

如果我想让程序只处理正 N 值但也找到负倍数，我可以只打印 i 和 j 的负数版本，因为你只能通过将两个正数或两个负数在一起。

行得通，但现在我想让这段代码处理负 N 值。例如，N = -10 的预期输出为：(-1, 10), (1, -10), (2, -5), (-2, 5);

问题是，上面的算法只能找到正数的正约数，因为它涉及平方根，它只为正数定义，循环从正数开始到正数结束。

我注意到我可以只计算 N 的绝对值的平方根，然后使循环从 -root 开始并在 root 结束以遍历 N 的负因数。不过，我必须确保跳过 0，因为没有定义 0 的除法，这导致它崩溃。我最终得到的代码如下所示：

#include <iostream>
#include <cmath>

int main()
{
    int n;
    std::cin >> n;

    int root_n = std::sqrt(std::abs(n));
    for(int i = -root_n; i <= root_n; i++)
    {
        if(i == 0 || n % i != 0)
            continue;

        int j = n / i;  
        std::cout << i << ", " << j << std::endl;
    }

    return 0;
}

它适用于我提出的所有测试，但我不确定这是否是最好的编写方式。有什么我可以改进的地方吗？

提前致谢！

编辑： 按照 Caleth 的建议尝试使用 std::div（也在 VS 中使用 ReSharper 插件给我重构建议）：

#include <iostream>
#include <cstdlib>

int main()
{
    int n;
    std::cin >> n;

    const int sqrt_n = std::sqrt(std::abs(n));
    for(auto i = -sqrt_n; i <= sqrt_n; i++)
    {
        if (i == 0)
            continue;

        const auto div_res = std::div(n, i);
        if (div_res.rem)
            continue;

        std::cout << i << ", " << div_res.quot << std::endl;
    }

    return 0;
}

不是计算余数，然后计算商，我可以只调用 std::div，returns 一个包含两个值的结构。

Answer 1

一个主要的观察结果是一个数的负约数和正约数是相同的，除了符号不同。如果你只看正数并自己处理符号，你可以节省一半的时间。例如，

int main()
{
    int n;
    std::cin >> n;

    int root_n = std::sqrt(std::abs(n));

    for(int i = 1; i <= root_n; i++) \ don't loop over negative numbers now
    {
        if(n % i != 0) \ not necessary to check for 0 anymore
            continue;

        int j = n / i;  
        std::cout << i << ", " << j << "\n";
        std::cout << -i << ", " << -j << "\n";  \ corresponding negative
    }

    return 0;
}

您可能会注意到我删除了 std::endl --- 您真的不需要经常刷新流。让输出随心所欲地缓冲会更快。

如果您正在寻找其他方法来修改您的程序，您可以尝试找到质因数分解，然后从中计算除数列表。对于大型、高度复合的输入，这会更快。但也有很大的不同。

获取将数字表示为两个整数乘积的所有方法

Get all ways to express a number as a product of two integers

c++

factors