反着枚举，这样更快，而且不用判是否为质数，题中说了。 @[zyh071](/user/995589)
by lczcy1 @ 2024-03-31 09:26:46
从一到n枚举。
by lczcy1 @ 2024-03-31 09:27:12
过了的话麻烦关注一下
by lczcy1 @ 2024-03-31 09:27:39
没过@我
by lczcy1 @ 2024-03-31 09:27:52
时间复杂度错误。
当 $p=\Theta\left(\sqrt n\right)$ 时，你的做法 for 循环将会执行 $n-p+1=\Theta(n)$ 次，时间复杂度为 $\Theta(n)$，由于 $n=2\times10^9$ ，此方法无法通过本题。
而枚举较小的质因数（即 $\frac np$）时间复杂度为 $\Theta\left(\sqrt n\right)$，可以通过本题。
做一道题前一定要先检查自己程序的时间复杂度。
by lcyxds @ 2024-04-08 21:26:59