c# - 是否有一种已知的快速算法来查找与给定数字相乘的所有数字对？

Question

例如，16 的倍数对是 {(16,1), (2,8), (4,4)} 和乘以 15 是 {(15,1), (5,3)} 但我不知道如何构建比蛮力更好的算法。我的方法看起来像

    private static IEnumerable<Tuple<int, int>> Multipliers(int m)
    {
        var found = new HashSet<int>();
        foreach(int v in Enumerable.Range(1, m))
        {
            int d = m / v;
            bool even = m % v == 0;
            if(even && found.Contains(d))
            {
                yield return Tuple.Create(d, v);
            }
            found.Add(v);
        }
    }

这很草率，可能效率不高。

Answer 1

这是给你的一个示例方法，但我不确定它本身是否是“最有效的方法”:

public static IEnumerable<(int A, int B)> Multipliers(int m)
{
    yield return (m, 1);

    int i = 2;
    int lastVal = m / 2;
    while (i <= lastVal)
    {
        if (m % i == 0)
        {
            lastVal = m / i;
            yield return (lastVal, i);
        }

        i++;
    }
}

public static void Main(string[] args)
{
    foreach (var pair in Multipliers(16))
    {
        Console.WriteLine("{0}, {1}", pair.A, pair.B);
    }
}

使用 C#7 元组返回语法，因为我可以。 :P

编辑:从 for 切换循环到 while循环处理 when m <= 2 的情况.

编辑 2: 正如 Adwaenyth 所建议的，这是检查是否 m 的方法的中间版本甚至。如果不是，则跳过所有潜在因素。另外，正如其他答案所建议的那样，将迭代限制为 m 的平方根。而不是 m/2 :

public static IEnumerable<(int A, int B)> Multipliers(int m)
{
    yield return (m, 1);

    int lastVal = (int)Math.Sqrt(m);
    int increment = (m % 2 != 0) ? 2 : 1;
    int i = (m % 2 != 0) ? 3 : 2;

    while (i <= lastVal)
    {
        if (m % i == 0)
        {
            lastVal = m / i;
            yield return (lastVal, i);
        }

        i += increment;
    }
}

我非常确定这种特定方法的效率是最高的。为了让它变得更好，您可以调整它以检查所有质数及其倍数直到 m 的平方根。 .理想情况下，您将针对查找表执行此操作，因为在生成素数时，您通过仅比较素数节省的大量时间会丢失。 (对于非常大的 m s，它仍然会更快地出现。)

EDIT 3 我发现我之前的代码使用了 lastVal使所需的时间有点不一致，并引入了一个奇怪的错误，有时会忘记检查更大的因素。这是一个应该可以解决这些问题的更新:

public static IEnumerable<(int A, int B)> Multipliers(int m)
{
    yield return (m, 1);

    int finalVal = (int)Math.Sqrt(m);
    int increment = m % 2 != 0 ? 2 : 1;
    int i = m % 2 != 0 ? 3 : 2;

    while (i <= finalVal)
    {
        if (m % i == 0)
        {
            yield return (m / i, i);
        }

        i += increment;
    }
}