首页 >web前端 >js教程 >javascript怎么求素数

javascript怎么求素数

青灯夜游
青灯夜游原创
2022-09-20 11:59:204374浏览

求素数的方法:1、遍历1~n区间中的所有自然数给n来除,若余数为0则表示该数n不是素数,否则就是素数,语法“for(i=2;i5af19ed287589000ea46aa3b5ec732c1 1;   }     for (let i = 2; i 473403c6b9575c622b9ebe6067a56cab 1;   }     for (let i = 2; i 5d84a44e85fad21b64a1a98595da400c 1;   }     if (n % 2 === 0) {     return false;   }     for (let i = 3; i e4ebc73d51900390b2034910a358a72c 1;   }     for (let i = 3; i 2fa1a152003a477da9b77bb1ab80f363= 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 03a568b98383134c20bbb7dc9f7d8b51 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