要检验一个数是不是质数,为什么我们要检验它是否只能被这个数的平方根整除?
当前回答
任何合数都是质数的乘积。
假设n = p1 * p2,其中p2 > p1,它们都是质数。
如果n % p1 === 0,则n是一个合数。
如果n % p2 === 0,那么猜猜n % p1 === 0 !
因此,如果n % p2 === 0,同时n % p1 !== 0,这是不可能的。 换句话说,如果一个合数n能被 p2、p3……PI(较大因子)也要除以最小因子p1。 事实证明,最低因子p1 <= Math.square(n)总是正确的。
其他回答
假设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不是质数。
如果一个数n不是质数,它可以被分解成两个因子a和b:
n = a * b
现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,n一定是质数。
设n是非素数。因此,它至少有两个大于1的整数因子。设f是n个这样的因子中最小的。设f >√n,则n/f是一个≤√n的整数,因此小于f,因此f不可能是n的最小因子。反证法;N的最小因子必须≤根号N。
假设我们有一个数字“a”,它不是质数[非质数/合数的意思是-一个可以被除1或它本身以外的数字整除的数字。例如,6可以被2或3整除,也可以被1或6整除。
6 = 1 × 6或6 = 2 × 3
如果a不是质数那么它可以被另外两个数除我们设这两个数是b和c。这意味着
a = b * c。
现在如果b或c,它们中的任何一个大于a的平方根那么b和c的乘积就会大于a。
因此,“b”或“c”总是<=“a”的平方根来证明方程“a=b*c”。
由于上述原因,当我们测试一个数字是否是质数时,我们只检查到该数字的平方根。
是的,正如上面所解释的,迭代到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>