PHP程序员小白到大牛集训(12期免息)
首页 >web前端 >js教程 > 正文

javascript怎么求素数

原创2022-09-20 11:59:20740 + Vue前端学习QQ群(点击入群)

求素数的方法:1、遍历1~n区间中的所有自然数给n来除,若余数为0则表示该数n不是素数,否则就是素数,语法“for(i=2;i<n;i++){if(n%i===0){return false;}}”。2、利用素数平方根范围,语法“for(i=2;i<=Math.sqrt(n);i++){if(n%i===0){return false;}}”。

前端(vue)入门到精通课程:进入学习
API 文档、设计、调试、自动化测试一体化协作工具:点击使用

本教程操作环境:windows7系统、javascript1.8.5版、Dell G3电脑。

素数的概念

素数又叫质数,素数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。

100以内的素数:2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97,共计25个。

JavaScript判定素数的四种方法

1、素数只能被1和自身整除

素数只能被1和自身整除,所以遍历(1,n)开区间中的所有自然数给n来除,若存在整除,即余数为0,则表示该数n不是素数,否则就是素数。

function isPrime(n) {
  n = parseInt(n);
 
  if (n <= 3) {
    return n > 1;
  }
 
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}
登录后复制

但是这种算法的复杂度为O(n)

2、素数平方根范围

假设n不是素数,则n除了可以被1和n整除外,还可以被i、j整除,即 n / i = j...0,比如15不是素数,15 / 3 = 5,比如35不是素数,35 / 5 = 7,此时i,j必然分别处于(1, Math.sqrt(n)]和[Math.sqrt(n), n) 之中,比如Math.sqrt(15) ≈ 3.8,则 3处于(1,3.8],5处于[3.8, 15)。比如Math.sqrt(4) = 2,则2处于(1,2]中,也处于[2,4)中。

function isPrime(n) {
  n = parseInt(n);
 
  if (n <= 3) {
    return n > 1;
  }
 
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}
登录后复制

此时算法复杂度为O(sqrt(n))

3、素数不能非2的其他偶数

除了2,所有偶数都不是素数

1.png

function isPrime(n) {
  n = parseInt(n);
 
  if (n <= 3) {
    return n > 1;
  }
 
  if (n % 2 === 0) {
    return false;
  }
 
  for (let i = 3; i <= Math.sqrt(n); i += 2) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}
登录后复制

for循环中n,只能为上图浅蓝色部分。

因此上面算法减少了一半的循环,时间复杂度为O(sqrt(n) / 2)

需要注意的是,本算法的代码不能将n % 2 === 0 的判断条件加入到循环中,如下代码存在漏洞

function isPrime(n) {
  n = parseInt(n);
 
  if (n <= 3) {
    return n > 1;
  }
 
  for (let i = 3; i <= Math.sqrt(n); i += 2) {
    if (n % 2 === 0 || n % i === 0) {
      return false;
    }
  }
  return true;
}
登录后复制

此时4、6、8都会被判定为素数。

漏洞形成的原因是,for循环的循环条件 i <= Math.sqrt(n) 不成立,比如n=4时,i <= Math.sqrt(4) 不成立,导致n无法进入循环中n % 2 === 0 的判断,而是直接退出循环,return true。

该算法只能保证循环条件 i <= Math.sqrt(n) 成立的n值判断素数正确,即 n >= i^2 = 9 时。

4、大于等于5的素数一定和6的倍数相邻

大于等于5的素数一定和6的倍数相邻

(注意这句话不等价于:和6的倍数相邻的数一定是大于5的素数,该结论不成立。)

2.png

如上图中,将大于等于5的数分为了:6y-1、6y、6y+1、6y+2、6y+3、6y+4(y>=1)

其中,6y、6y+2、6y+3、6y+4都不可能是素数,只有6y-1和6y+1可能是素数。

另外,6y-1(y>=1)和 6y + 5 (y>=0)等价。

所以,我们可以将n不为6y-1(或6y+5)和6y+1的数直接排除,排除方法为,

  if (n % 6 !== 1 && n % 6 !== 5) {
    return false;
  }
登录后复制

下面要剔除掉6y-1(或6y+5)和6y+1中的非素数,

  for (let i = 5; i <= Math.sqrt(n); i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
登录后复制

这里大家比较疑惑的可能有两点:

  • for循环i自增为啥是 6
  • for循环中素数判定的条件为啥是 n % i === 0 || n % (i+2) === 0

3.png

我们看上面图解,可以发现,6y-1,是基数为5,差值为6的等差数列,即 5 + 6x :

  • 对于 5 + 6x 而言,如果x为5的倍数(5 * z),则5 + 6x = 5 + 6 * 5 * z = 5 *(1+6z),则此时5 + 6x可以被5整除
  • 5 + 6x 还可以转化为 5 + 6 + 6 * (x-1) = 11 + 6(x-1),则只要x-1为11的倍数,则5 + 6x可以被11整除
  • 5 + 6x 还可以转化为 5 + 12 + 6 * (x-2) = 17 + 6(x-2),则只要x-2为17的倍数,则5 + 6x可以被17整除
  • ......

6y+1,是基数为7,差值为6的等差数列,即 7 + 6x :

  • 对于 7 + 6x 而言,如果x为7的倍数(7 * z),则7 + 6x = 7 + 6 * 7 * z = 7 *(1+6z),则此时7 + 6x可以被7整除
  • 7 + 6x 还可以转化为 7 + 6 + 6 * (x-1) = 13 + 6(x-1),则只要x-1为13的倍数,则7 + 6x可以被13整除
  • 7 + 6x 还可以转化为 7 + 12 + 6 * (x-2) = 19 + 6(x-2),则只要x-2为19的倍数,则7 + 6x可以被19整除
  • ......

所以6y-1和6y+1可能整除的数自增量为6,这是for循环i自增为啥是 6的原因

且6y-1和6y+1的整除数基数为5和7,相差为2,这是for循环中素数判定的条件为啥是 n % i === 0 || n % (i+2) === 0的原因

function isPrime(n) {
  n = parseInt(n);
 
  if (n <= 3) {
    return n > 1;
  }
 
  if (n % 6 !== 1 && n % 6 !== 5) {
    return false;
  }
 
  for (let i = 5; i <= Math.sqrt(n); i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
 
  return true;
}
登录后复制

此时时间复杂度为 O(sqrt(n) / 3)

【相关推荐:javascript视频教程编程基础视频

以上就是javascript怎么求素数的详细内容,更多请关注php中文网其它相关文章!

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

  • 相关标签:javascript 素数
  • 程序员必备接口测试调试工具:点击使用

    Apipost = Postman + Swagger + Mock + Jmeter

    Api设计、调试、文档、自动化测试工具

    后端、前端、测试,同时在线协作,内容实时同步

    支持grpc,http,websocket,socketio,socketjs类型接口调试

    相关文章

    相关视频


    视频教程分类

    专题推荐

    官方公众号

    php中文网课程

    扫码关注官方公众号
    回复“phpcn01”领取php学习资料课程
    全套工具、电子书、脑图、内部课程等

    推荐视频教程

    开通VIP会员课 0元学

    热门推荐