Js关于质数的判定

JavaScript025

Js关于质数的判定,第1张

验证是否为大于1 的自然数

方法一: 根据质数定义判定

方法二: 通过合数判定

方法一直观明了,但是运算量过大。通过定义可知大于1的自然数 不是质数就是合数 ,因此可以通过判断合数来进行优化。

假设num是个合数,它必然是两数之积,即 num = a*b ,且a,b均为不为1的正整数,a,b要么一大一小,要么相等。当a为最小值2时,b有最大值,即合数的最大因数为num/2,最小因数为2。换句话说一个数在2到num/2之间范围内有因数为合数,没因数为素数。

上面的方式是通过最大因数判断,还可以继续优化减少运算。

合数num为它的两个平方根之积,即num =* ,num=a*b,当a,b不相等时,一个大于 ,一个小于 ,即合数num较小的因数范围为2到 之间。

首先什么质数? 质数就是大于一的自然数中,只能被自己和1整除的数。了解了这个 很容易就能写出判断条件

普通写法:

利用算法的写法:

原理:一个数如果可以进行因数分解,那么必定一个因数<=他的平方根 另一个因数>=他的平方根 那么只需要从2开始 到平方根为止,如果能被整除 就代表不是质数。 (拿16举例,只要能被2整除就代表能被8整除所以只用判断一边)

参考下面代码

function isprime(x)

{

for(var i = 2i <sqrt(x)i++)

if(isdiv(x, i) == 0) return false

return true

}