javascript怎么求素数

function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 2; i <p>但是这种算法的复杂度为O(n)</p><h3 id="%E7%B4%A0%E6%95%B0%E5%B9%B3%E6%96%B9%E6%A0%B9%E8%8C%83%E5%9B%B4"><strong>2、素数平方根范围</strong></h3><p>假设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)中。</p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 2; i <p>此时算法复杂度为O（sqrt(n)）</p><h3 id="%E7%B4%A0%E6%95%B0%E4%B8%8D%E8%83%BD%E6%98%AF%E9%99%A4%E4%BA%862%E5%A4%96%E7%9A%84%E5%81%B6%E6%95%B0"><strong>3、素数不能非2的其他偶数</strong></h3><p>除了2，所有偶数都不是素数</p><p><img src="https://img.php.cn/upload/image/644/149/762/1663645614907138.png" title="1663645614907138.png" alt="1.png"></p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  if (n % 2 === 0) {
    return false;
  }
 
  for (let i = 3; i <p>for循环中n，只能为上图浅蓝色部分。</p><p>因此上面算法减少了一半的循环，时间复杂度为O（sqrt(n) / 2） </p><p>需要注意的是，本算法的代码不能将n % 2 === 0 的判断条件加入到循环中，如下代码存在漏洞</p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 3; i <p>此时4、6、8都会被判定为素数。</p><p>漏洞形成的原因是，for循环的循环条件 i </p><p>该算法只能保证循环条件   i = i^2 = 9 时。</p><h3 id="%E5%A4%A7%E4%BA%8E%E7%AD%89%E4%BA%8E5%E7%9A%84%E7%B4%A0%E6%95%B0%E4%B8%80%E5%AE%9A%E5%92%8C6%E7%9A%84%E5%80%8D%E6%95%B0%E7%9B%B8%E9%82%BB"><strong>4、大于等于5的素数一定和6的倍数相邻</strong></h3><p>大于等于5的素数一定和6的倍数相邻</p><p>（注意这句话不等价于：<span style="text-decoration:line-through;">和6的倍数相邻的数一定是大于5的素数</span>，该结论不成立。）</p><p><img src="https://img.php.cn/upload/image/346/360/896/1663645626679081.png" title="1663645626679081.png" alt="2.png"></p><p>如上图中，将大于等于5的数分为了：6y-1、6y、6y+1、6y+2、6y+3、6y+4（y&gt;=1）</p><p>其中，6y、6y+2、6y+3、6y+4都不可能是素数，只有6y-1和6y+1<strong><span   style="max-width:90%">可能</span></strong>是素数。</p><p>另外，6y-1（y&gt;=1）和 6y + 5 （y&gt;=0）等价。</p><p>所以，我们可以将n不为6y-1（或6y+5）和6y+1的数直接排除，排除方法为，</p><pre class="brush:js;toolbar:false">  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;
    }
  }

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;
}