for(int i=1;i*i<=n;i++)这个是为什么

for(int i=1;i*i<=n;i++)这个是为什么

warren_au 2020-08-12

源自：线性查找法 2-8 常见的时间复杂度

75

收起

2回答

liuyubobobo 回答被采纳获得+3积分 2020-08-12 19:51:52

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

warren_au 提问者 #1

为什么i*i<=n在这里可以这么简写，表达i和i/n有两个约数

2020-08-13 19:12:33
liuyubobobo 回复提问者 warren_au #2

i * i <= n 表示我们搜索到 sqrt(n) 就够了。比如要想找到 10 的约束，我们搜索到 3 就够了。因为大于 3 的约数，肯定在找更小的约数的时候，顺便找到了。比如 5 这个约数，肯定找到 2 的时候，我们就知道了 10 / 2 = 5 也是另一个约数。

2020-08-14 05:16:51
warren_au 提问者回复 liuyubobobo #3

在找更小的约数的时候，顺便找到另外一个数字，这个跟i * i 有什么关系吗，不太能理解之间的关联，为什么i * i <= n可以用来表达以上关系呢？

2020-08-15 11:12:52

点开查看后面2条评论

假蛙工程师 2021-10-10 15:43:02

一个正整数的约束就是该数可以整除的数，例如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

相似问题

老师您好，为什么i=i+j在for循环括号里面和外面，输出的结果不一样？

执行语句for（int i=1；i++<4；）；后变量i的值为（）?

for循环i的值

请问这里的++$i和$i++有什么区别？

i=4然后i- -不就是3了吗，为什么i- ->3还能成立

登录后可查看更多问答，登录/注册

算法与数据结构

参与学习 2583 人
解答问题 1082 个

慕课网算法名师Liuyubobobo，5年集大成之作从0到工作5年，算法与数据结构系统解决方案

本课精华内容

问答作业

应对Java工程师面试中的算法部分,需要学习的重点,非重点章节

102 3

希望老师可以为我找计算机相关工作提一些建议，感谢！

74 3

学习规划问题

388 2

一个关于专业的问题

235 3

siftDown函数问题

38 18

查看更多本课问答

请稍等 ...

意见反馈帮助中心 APP下载