Algo 获取 Integer.MAX_VALUE 的超时

Question

我有一个算法，它提供了从1到N的整数的因子。代码如下提供，

public static int solution(int N) {
int count = 0;
for (int i = 1; (i * i) <= N; i++) {
if (i * i == N) {
count++;
return count;
}
if (N % i == 0) {
count += 2;
}
}
return count;
}

这工作正常，但是，显然会中断整数的非常大的值，例如Integer.MAX_VALUE.如何改进"非常大"值的代码？

Answer 1

只需按如下所示更改您的 for 循环条件，它应该可以工作。

for (int i = 1; (i * i) > 0 && (i * i) <= N; i++) {

之所以需要此更改，是因为在46341处发生溢出，并且此数字中的任何平方都会导致负值(很可能，因为溢出是一种未定义的行为(并导致满足(i * i) <= N条件并且循环继续。因此，只需添加一个额外的检查，即正方形应> 0 来处理这种情况。

Answer 2

如果N == Integer.MAX_VALUE，(i * i) <= N将始终true，因为int乘法的结果不能高于Integer.MAX_VALUE。因此，循环永远不会终止。

您可以将i更改为long，这将支持更大的N值。

Answer 3

您可以将算法更改为除以i而不是乘以i，以便输入始终以最大数字。 这将允许Integer.MAX_VALUE在不更改数据类型的情况下运行：

public static int solution(int N) {
int count = 0;
for (int i = 1; (N / i) >= i; i++) {
if (N / i == i) {
count++;
return count;
}
if (N % i == 0) {
count += 2;
}
}
return count;
}

请注意，for条件和前if条件现在已(N / i) >= i和N / i == i，它们将具有与以前相同的功能。

Answer 4

@vivek_23提供的答案是正确的，但是，我们也可以将条件中的容器转换为long作为(long) i * i <= N，这将解决问题，

public static int solution(int N) {
int result = 0;

// int i = 46341;
for (int i = 1; (long) i * i <= N; i++) {
/*
* we only have one factor
* */
if (i * i == N) {
return ++result;
}
/*
* we get 2 factors/ divisors ie i and (N/i)
* */
else if (N % i == 0) {
result += 2;
}
}
return result;
}