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

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，它返回一个包含两个值的结构。

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 ---你真的不需要经常刷新流。允许输出缓冲区更快。

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