要检验一个数是不是质数,为什么我们要检验它是否只能被这个数的平方根整除?
当前回答
如果一个数n不是质数,它可以被分解成两个因子a和b:
n = a * b
现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,n一定是质数。
其他回答
因为如果一个因子大于根号n,那么与它相乘等于n的另一个因子必然小于根号n。
如果一个数n不是质数,它可以被分解成两个因子a和b:
n = a * b
现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,n一定是质数。
是的,正如上面所解释的,迭代到Math就足够了。对一个数的平方根取底,以检查其质数(因为SQRT涵盖了所有可能的除法情况;和数学。因为任何高于SQRT的整数已经超出了它的范围)。
下面是一个可运行的JavaScript代码片段,它代表了这种方法的简单实现-它的“运行时友好性”足以处理相当大的数字(我试着检查质数和非质数,最大可达10**12,即1万亿,将结果与在线质数数据库进行比较,即使在我的廉价手机上也没有遇到错误或延迟):
function isPrime(num) { if (num % 2 === 0 || num < 3 || !Number.isSafeInteger(num)) { return num === 2; } else { const sqrt = Math.floor(Math.sqrt(num)); for (let i = 3; i <= sqrt; i += 2) { if (num % i === 0) return false; } return true; } } <label for="inp">Enter a number and click "Check!":</label><br> <input type="number" id="inp"></input> <button onclick="alert(isPrime(+document.getElementById('inp').value) ? 'Prime' : 'Not prime')" type="button">Check!</button>
假设n不是一个质数(大于1),那么有数字a和b满足
n = ab (1 < a <= b < n)
通过将a<=b的关系乘以a和b,我们得到:
a^2 <= ab
ab <= b^2
因此:(注意n=ab)
a^2 <= n <= b^2
因此:(注意a和b是正的)
a <= sqrt(n) <= b
因此,如果一个数(大于1)不是质数,并且我们测试到该数的平方根的可除性,我们将找到其中一个因数。
假设m =根号n,那么m × m = n。如果n不是质数,那么n可以写成n = a × b,所以m × m = a × b。注意,m是实数,而n、a和b是自然数。
现在有三种情况:
A > m⇒b < m ⇒A = m, b = m A < m⇒b > m
在这三种情况下,min(a, b)≤m。因此,如果我们搜索到m,我们一定会找到n的至少一个因子,这足以证明n不是质数。
推荐文章
- 如何用动态规划确定最长递增子序列?
- 在c++程序中以编程方式检测字节序
- 理解递归
- 段树、区间树、二叉索引树和范围树之间有什么区别?
- 给定一个数字,找出下一个与原始数字具有完全相同的数字集的更高的数字
- HSL到RGB的颜色转换
- 使用Java在原语数组中查找最大/最小值
- 好的Java图算法库?
- 什么时候我应该使用Kruskal而不是Prim(反之亦然)?
- 取一个集中在中心的随机数
- 如何计算圆周长上的一点?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下,您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 如何使用JavaScript比较软件版本号?数量(只)