N的最大除数（不包括在内）

Question

我正在尝试将列表划分为尽可能大的子列表。如果列表不能以这种方式划分，我将根据需要处理它，但我需要获得除N本身之外的最大数量，均匀地划分N.

我写了一个非常天真的解决方案，但我觉得应该有一个公式或者什么东西可以在不断的时间内完成。我的列表不是那么大，最大大小是1000.这可能不是关键路径，但有更好的算法吗？

public static int largestDivisor(int n){
   int divisor = 0;
   for (int i = 1; i <= n/2; i++)
       if (n % i == 0) 
           divisor = i;

   return divisor; 
}

Answer 1

反向迭代值。只需返回您找到的第一个（它将是最好的）。就像是，

public static int largestDivisor(int n) {
    for (int i = n / 2; i >= 2; i--) {
        if (n % i == 0) {
            return i;
        }
    }
    return 1;
}

或者，你可能会对@WillemVanOnsem的answer略有改进，并从像奇怪的值开始;

public static int largestDivisor(int n) {
    if (n % 2 == 0) {
        return n / 2;
    }
    final int sqrtn = (int) Math.sqrt(n);
    for (int i = 3; i <= sqrtn; i += 2) {
        if (n % i == 0) {
            return n / i;
        }
    }
    return 1;
}

Answer 2

我不知道你是否可以在不变的时间内完成这项工作，但你可以在更短的时间内完成这项工作。

从2开始，遍历所有数字，检查n是否可被该数字整除。当你得到一个除以n的数字，那么你可以停止 - 你的答案是n / i。如果你到达最后它仍然没有分裂，那么n是素数，答案只有1。

如果你没有找到除数，你可以用√n结束，而不是以n / 2结尾，这将减少大O.

此外，您可以先检查它是否可以被2整除，然后转到3并仅检查那里的奇数。 （如果它被一个偶数整除，则它可以被2整除。）这不会改变大O，但它应该将处理时间减少一半，因为你只检查了一半的除数。

Answer 3

你知道如果a可以被b分割，它也可以被a / b整除，而b越小，a / b就越大，所以一旦你找到了除数，就返回qazxsw poi：

n/divisor

这也更快，因为：

1. 除数越多，它们就会变得越稀少;和
2. 你已经可以放弃在

   public static int largestDivisor(int n){
       for(int i = 2; i <= n/2; i++)
           if(n % i == 0) {
               return n/divisor;
           }
       }
       return 0; //or whatever you decide to return if there is no such divisor
   }

   。

所以最有效的方法是：

sqrt(n)