Apakah algoritma untuk mencari nombor perdana dalam JavaScript?

Nombor perdana ialah integer positif yang hanya boleh dibahagi sama rata dengan 1 dan dirinya sendiri. Algoritma untuk mencari nombor perdana adalah masalah yang sangat asas dan penting dalam sains komputer Ia boleh digunakan untuk banyak bidang, seperti penyulitan, pemampatan data, dll.

Dalam JavaScript, sangat mudah untuk melaksanakan algoritma untuk mencari nombor perdana. Di bawah saya akan memperkenalkan dua kaedah:

1. Kaedah penghakiman nombor perdana

Kaedah ini merupakan kaedah paling asas untuk mencari nombor perdana Prinsipnya adalah untuk menilai sama ada integer positif hanya boleh Dibahagi dengan 1 dan dirinya sendiri. Kaedah pelaksanaan khusus adalah seperti berikut:

function isPrime(n) {
  if (n <= 1) {
    return false; // 1和0都不是素数
  }

  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false; // 如果n能被i整除，则n不是素数
    }
  }

  return true; // n是素数
}

Fungsi ini menerima integer positif n sebagai parameter Jika n ialah nombor perdana, ia mengembalikan benar, jika tidak ia mengembalikan palsu. Kerumitan masanya ialah O(n), yang tidak optimum. Jika anda perlu menilai sejumlah besar nombor perdana, disyorkan untuk menggunakan Ayak Eratosthenes yang diperkenalkan di bawah.

2. Ayak Eratosthenes

Kaedah ini membuang nombor komposit melalui satu siri ayak, hanya meninggalkan nombor perdana. Kaedah pelaksanaan khusus adalah seperti berikut:

function getPrimes(n) {
  let arr = new Array(n + 1).fill(true); // 先创建一个全为 true 的数组，代表是素数
  let primes = [];

  for (let i = 2; i <= n; i++) {
    if (arr[i]) {
      primes.push(i); // i 是素数，添加到 primes 数组中
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false; // 将 i 的倍数都标记为不是素数
      }
    }
  }

  return primes;
}

Fungsi ini menerima integer positif n sebagai parameter dan mengembalikan tatasusunan nombor perdana kurang daripada atau sama dengan n. Kerumitan masanya ialah O(n log log n), yang lebih pantas daripada kaedah penghakiman nombor perdana.

Kesimpulan

Di atas adalah dua kaedah mencari nombor perdana dalam JavaScript Walaupun pelaksanaannya mudah, ia sangat praktikal. Jika anda berminat dengan nombor perdana, anda boleh cuba mengoptimumkan kedua-dua kaedah ini untuk menjadikannya lebih pantas dan cekap.

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