Bagaimana untuk mencari nombor perdana dalam javascript

Cara mencari nombor perdana: 1. Lintas semua nombor asli dalam julat 1~n dan bahagikan dengan n Jika bakinya ialah 0, ia bermakna nombor n bukan nombor perdana, sebaliknya ia adalah nombor perdana. Sintaks "untuk(i=2 ;i

Persekitaran pengendalian tutorial ini: sistem Windows 7, versi JavaScript 1.8.5, komputer Dell G3.

Konsep nombor perdana

Nombor perdana juga dipanggil nombor perdana Nombor perdana merujuk kepada nombor yang lebih besar daripada 1 dan tidak boleh dibahagikan dengan yang lain nombor asli kecuali 1 dan dirinya sendiri.

Nombor perdana dalam 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 secara keseluruhan.

Empat cara untuk menentukan nombor perdana menggunakan JavaScript

1 nombor perdana hanya boleh dibahagi dengan 1 dan nombor itu sendiri

Nombor perdana boleh sahaja Ia boleh dibahagikan dengan 1 dan dirinya sendiri, jadi semua nombor asli dalam selang terbuka (1, n) dilalui dan dibahagikan dengan n Jika terdapat pembahagian integer, iaitu bakinya ialah 0, ia bermakna nombor n bukan nombor perdana, sebaliknya ia adalah nombor perdana.

function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 2; i <p>Tetapi kerumitan algoritma ini ialah O(n)</p><h3 id="strong-Julat-punca-kuasa-dua-nombor-perdana-strong"><strong>2 Julat punca kuasa dua nombor perdana</strong></h3><p>Andaikan n. bukan nombor perdana, maka Selain boleh dibahagi dengan 1 dan n, n juga boleh dibahagi dengan i dan j, iaitu, n / i = j...0 Sebagai contoh, 15 bukan nombor perdana, 15 / 3 = 5. Contohnya, 35 bukan nombor perdana, 35 / 5 = 7 , pada masa ini i, j mestilah dalam (1, Math.sqrt(n)] dan [Math.sqrt(n), n) masing-masing Sebagai contoh, Math.sqrt(15) ≈ 3.8, maka 3 adalah dalam (1, 3.8 ], 5 adalah dalam [3.8, 15). Sebagai contoh, Math.sqrt(4) = 2, maka 2 adalah dalam (1,2] dan juga dalam [2,4). </p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 2; i <p>Kerumitan algoritma pada masa ini ialah O(sqrt(n))</p><h3 id="strong-Nombor-perdana-tidak-boleh-menjadi-nombor-genap-selain-strong"><strong>3 Nombor perdana tidak boleh menjadi nombor genap selain 2</strong></h3><p>Kecuali 2. Semua nombor genap bukan nombor perdana </p><p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/image/644/149/762/1663645614907138.png" class="lazy" title="1663645614907138.png" alt="Bagaimana untuk mencari nombor perdana dalam javascript"></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> n dalam gelung for hanya boleh menjadi bahagian biru muda dalam gambar di atas. </p><p>Jadi algoritma di atas mengurangkan gelung sebanyak separuh, dan kerumitan masa ialah O(sqrt(n) / 2) </p><p>Perlu diambil perhatian bahawa kod algoritma ini tidak boleh n % 2 == Syarat penghakiman = 0 ditambahkan pada gelung Terdapat celah dalam kod berikut </p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 3; i <p>Pada masa ini, 4, 6, dan 8 semuanya akan dinilai sebagai nombor perdana. </p><p>Sebab kerentanan ialah keadaan gelung i </p><p>Algoritma ini hanya boleh menjamin bahawa nilai n bagi n apabila keadaan gelung i = i^2 = 9. </p><h3 id="strong-nombor-perdana-yang-lebih-besar-daripada-atau-sama-dengan-mesti-bersebelahan-dengan-gandaan-strong"><strong>4 nombor perdana yang lebih besar daripada atau sama dengan 5 mesti bersebelahan dengan gandaan 6</strong></h3><p>Nombor perdana yang lebih besar daripada atau sama dengan 5 mesti bersebelahan dengan gandaan 6. </p><p> (Perhatikan bahawa ayat ini tidak bersamaan dengan: nombor bersebelahan dengan <span style="text-decoration:line-through;"> dan gandaan 6 mestilah nombor perdana </span> lebih besar daripada 5. Kesimpulan ini tidak benar.) </p> <p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/image/674/593/865/1663645632699688.png" class="lazy" title="166364562667908Bagaimana untuk mencari nombor perdana dalam javascript" alt="Bagaimana untuk mencari nombor perdana dalam javascript"></p><p>Seperti yang ditunjukkan dalam gambar di atas, nombor yang lebih besar daripada atau sama dengan 5 dibahagikan kepada: 6y-1, 6y, 6y 1, 6y 2, 6y 3, 6y 4 (y> =1)</p><p>Antaranya, 6y, 6y 2 , 6y 3 dan 6y 4 tidak boleh menjadi nombor perdana, hanya 6y-1 dan 6y 1<strong><span   style="max-width:90%"> boleh</span></strong> menjadi nombor perdana . </p><p>Selain itu, 6y-1 (y>=1) dan 6y 5 (y>=0) adalah bersamaan. </p><p>Jadi, kita boleh terus mengecualikan nombor di mana n bukan 6y-1 (atau 6y 5) dan 6y 1. Kaedah penyingkiran ialah, </p><pre class='brush:php;toolbar:false;'>  if (n % 6 !== 1 && n % 6 !== 5) {
    return false;
  }

Yang berikut akan menghapuskan 6y- 1 (atau 6y 5) dan nombor bukan perdana dalam 6y 1,

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

Mungkin terdapat dua perkara yang anda keliru di sini:

• Mengapa gelung untuk i increment? 🎜>6
Mengapakah syarat untuk penentuan nombor perdana dalam gelung untuk n % i === 0 || n %
• (i 2) == = 0

Melihat rajah di atas, kita dapati bahawa 6y-1 ialah jujukan aritmetik dengan asas 5 dan beza 6, iaitu , 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视频教程、编程基础视频】

Atas ialah kandungan terperinci Bagaimana untuk mencari nombor perdana dalam javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!