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

反向迭代值。只需 return 您找到的第一个（它将是最棒的）。像，

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

或者，您可以对 @WillemVanOnsem's 稍作改进，并从 奇数值 开始，例如；

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

你知道如果a可以被b整除，它也可以被a/b整除，b越小，a/b越大，所以一旦找到除数，return n/divisor:

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

这也更快，因为：

除数越大，它们就越罕见；和
你已经可以在 sqrt(n) 放弃了。

所以最有效的方法是：

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

Answer 3

我不知道你是否可以在常数时间内完成，但你肯定可以在比这更短的时间内完成。

从 2 开始，遍历所有数字，检查 n 是否可以被该数字整除。当你得到一个整除 n 的数字时，你就可以停下来——你的答案是 n/i。如果走到尽头还是不除，那么n是质数，答案就是1。

如果找不到除数，不用在n/2处结束，用这个方法可以在√n处结束，这样会减少大O。

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

N 的最大约数（不包括它自己）

Largest Divisor of N (Excluding Itself)

java

int

division

modulus