我的算法学得很辣鸡(因为没有学),所以现在开始每 n 日基础算法课堂 233
Google 了一下什么是质数(对不起小学数学老师啊),然后知道了:
任何大于 1 且仅能被自身和 1 整除的自然数叫做质数(素数)
那么问题就是如何确定自然数 n 不能被除了 1 和自身的自然数整除,也就是要用 n 来一个个整除所有的自然数试试,而自然数可是无限的,阿姨!于是我们想缩小范围,确定一个范围的最小值和最大值:
在一般领域,对正整数 n,如果用 2 到
Math.sqrt(n)
之间的所有整数去除,均无法整除,则 n 为质数。
这样就极大地缩小了范围,不过是怎么得出结论的? 我想:
<= Math.sqrt(n)
,也就是判断它不是合数(即 <= Math.sqrt(n)
的自然数不是 n 的约数)那这里它就是质数那么我们是要循环 2 ~ Math.sqrt(n)
中的数来一个个整除吗?
当然不是,我们可以排除这里面的偶数,因为质数明显不能被偶数整除,当能被偶数整除时应提前返回 false
,并且循环的自增不是 1 而是 2,因为排除了最小的偶数 2,范围是 3 ~ Math.sqrt(n)
,自增 2 确保取所有奇数。
好的,Let the coding begin?
// PS. 这看起来和算法没半毛钱关系
Pay now to fund the work behind this issue.
Get updates on progress being made.
Maintainer is rewarded once the issue is completed.
You're funding impactful open source efforts
You want to contribute to this effort
You want to get funding like this too