2回答

liuyubobobo

2020-08-12

已采纳

抱歉，我没有理解你的问题。什么为什么？

3

hiuyubobobo

回复

harren_au

h 抱歉，刚才看错你的问题了。因为 i 和 n / i 都是约数，所以对于 n = a * b，我们只需要搜索所有的 a <= b 中的 a 就好了。换句话说，我们只需要搜索到 i <= sqrt(n) 就好了。因为 i 大过 sqrt(n)，另外一半肯定小于当前的 i，所以不满足上面说的 a <= b。i <= sqrt(n) 和 i * i <= n 等价。

h020-08-15

共5条回复

假蛙工程师

2021-10-10

一个正整数的约束就是该数可以整除的数，例如4，它的约数为1，2 ，4.

求一个数n的约数，可以使用遍历的方式将n把1到n除一遍。

也可以简单点的方法，约数几乎都是成对出现的，这是由于它的定义决定的。例如16/2=8 ，那么必然存在16/8=2;

a*b=n  假设a<=b  必有a<=sqrt(n) b>=sqrt，所以只需i<=sqrt即可，大于sqrt(n)的约数可以通过n/i求得到。

i<=sqrt(n) 两边同时平方，i*i <=n

1