我需要一个最佳算法来找到数字 N 的最大除数。最好在 C 或 C# 中

Question

我目前正在使用以下代码，但对于大量数据来说它非常慢

        static int divisor(int number)
        {
            int i;
            for (i = number / 2; i >= 1; i--)
            {
                if (number % i == 0)
                {
                    break;
                }
            }
            return i;
        }

原文由 Ronzii 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

首先认为您可以找到最小的除数 d（当然不等于 1），然后 N/d 将是您要查找的最大除数。

例如，如果 N 可以被 3 整除，那么您将需要 2 次迭代才能找到答案——在您的情况下，大约需要 N/6 次迭代。

编辑： 为了进一步改进你的算法，你可以只迭代奇数（在检查你的数字是否是偶数之后），或者更好的是，如果你预先计算了素数列表，那么你可以迭代它们，因为最小的除数显然是是一个素数。

原文由 Vladimir 发布，翻译遵循 CC BY-SA 3.0 许可协议