我需要一个最优算法来找到数字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;
        }

Answer 1

首先想到你可以找到最小的除数d(当然不等于1),那么N/d将是你正在寻找的最大除数.

例如,如果N可以被3整除,那么你将需要2次迭代来找到答案 - 在你的情况下,它将是大约N/6次迭代.

编辑:为了进一步改进你的算法,你可以只迭代奇数(在检查你的数字是否为偶数之后),或者更好的是,如果你有预先计算的素数列表,那么你可以迭代它们只是因为最小的除数很明显是素数.

Answer 2

不知道这是否是最佳解决方案，但您最好从2开始，然后向上攀升，例如：

  static int divisor(int number)
    {
        int i;
        for (i = 2; i <sqrt(number); i++)
        {
            if (number % i == 0)
            {
                break;
            }
        }
        return number/i;
    }

编辑

使它也能与质数一起使用：

 static int divisor(int number)
    {
        int i;
        for (i = 2; i <=sqrt(number); i++)
        {
            if (number % i == 0)
            {
                return number/i;
            }
        }
        return 1;
    }