Bagaimana untuk Cekap Menentukan sama ada Nombor adalah Perdana dalam JavaScript?

Semakan Nombor Utama dalam JavaScript

Artikel ini menangani masalah menentukan sama ada nombor yang diberikan adalah perdana atau tidak menggunakan JavaScript. Nombor perdana ialah integer yang lebih besar daripada 1 yang tidak boleh dibahagikan dengan mana-mana nombor asli lain kecuali 1 dan dirinya sendiri.

Penyelesaian 1

Kaedah tradisional melibatkan lelaran daripada 2 kepada punca kuasa dua nombor input dan menyemak sama ada nombor itu boleh dibahagikan dengan mana-mana daripada ini. Jika ya, ia bukan prima; jika tidak, ia adalah.

<code class="javascript">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true; // because 1 is not prime

for (let i = 2; i < inputValue; i++) {
  inputValue % i == 0 ? (isPrime *= false) : (isPrime *= true);
}

alert(`${inputValue} is ${isPrime ? 'prime' : 'not prime'} number`);

Kerumitan Masa: O(sqrt(n))
Kerumitan Angkasa: O(1)

Penyelesaian 2

Pendekatan alternatif menggunakan fakta bahawa nombor perdana yang lebih besar daripada 2 tidak boleh ganjil. Oleh itu, adalah memadai untuk menyemak kebolehbahagi dengan 2 dan kemudian dengan nombor ganjil sehingga punca kuasa dua nombor input. Pengoptimuman ini mengurangkan masa pelaksanaan dengan ketara.

<code class="javascript">const isPrime = num => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 == 0 || num % 3 == 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) return false;
  }
  return true;
};</code>

Kerumitan Masa: O(sqrt(n))
Kerumitan Ruang: O(1)

Atas ialah kandungan terperinci Bagaimana untuk Cekap Menentukan sama ada Nombor adalah Perdana dalam JavaScript?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!