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