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的答案进行一些改进，并以奇数开头，例如；

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;
}