简单的最大除数问题 c++ 实现抛出时间限制已超出

Question

我正在向我大学的测试人员提交代码，我的代码对于我提供的测试用例非常有效。

检查器抛出时间限制超出错误，我正在 Visual Studio 中进行测试，这与在线法官编译器完全兼容。

#include <iostream>
#include <math.h>
using namespace std;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int i, n, gd; cin >> n;
gd = 1;
if (n > 1) {
for (i = 2; i < n; i++)
{
if (n % i == 0)
{
gd = i;
}
}
cout << gd;
}
return 0;
}
}

我找不到为什么它会引发这样的错误。谢谢

该代码只能在我的可视化工作室中工作，但无法通过测试。顺便说一下，检查器隐藏了测试用例。

Answer 1

与其找到最大除数，不如寻找最小的除数d(其中d > 1(。那么最大的除数是n/d.

你可以用一个简单的循环来做到这一点，就像你找到第一个除数时breaks一样。循环在经过sqrt(n)时可以停止，在这种情况下，数字是质数。

在最坏的情况下，这更快，因为它将迭代次数限制为 sqrt(n(。在d较小的常见情况下，只需很少的操作。