Bagaimana untuk mengira nombor perdana dalam javascript

Nombor perdana merujuk kepada integer positif yang hanya boleh dibahagikan dengan 1 dan ianya merupakan konsep penting dalam matematik dan digunakan secara meluas dalam sains komputer. Dalam Javascript, kita boleh menggunakan kaedah berikut untuk mengira nombor perdana.

1. Kaedah penghitungan ganas

Kaedah penghitungan ganas ialah kaedah pengiraan nombor perdana yang mudah dan langsung. Kita boleh bermula dari 2 dan melintasi ke n-1, dan menentukan sama ada setiap integer boleh membahagi n. Jika terdapat integer m yang membahagi n, maka n bukan perdana. Jika n tidak boleh dibahagikan dengan setiap integer m, maka n ialah nombor perdana.

Berikut ialah kod pelaksanaan Javascript kaedah penghitungan brute force:

function isPrime(num) {
  if (num < 2) {
    return false;
  }
  
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  
  return true;
}

2. Ayak Eratosthenes

Ayak Eratosthenes ialah cara yang lebih pantas untuk kaedah mengira nombor perdana. Idea asasnya ialah menyusun dahulu semua integer positif mengikut tertib, dan kemudian menapis nombor yang boleh dibahagikan dengan 2 bermula dari 2, kemudian menapis nombor yang boleh dibahagikan dengan 3, kemudian menapis nombor yang boleh dibahagikan dengan 5, dan seterusnya , sehingga tiada lagi nombor perdana boleh ditapis.

Berikut ialah kod pelaksanaan Javascript Sieve of Eratosthenes:

function sieveOfEratosthenes(n) {
  const primes = new Array(n + 1).fill(true);

  primes[0] = false;
  primes[1] = false;

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes.reduce((acc, cur, index) => {
    if (cur) {
      acc.push(index);
    }

    return acc;
  }, []);
}

3. Algoritma Miller-Rabin

Algoritma Miller-Rabin ialah nombor perdana kebarangkalian Algoritma ujian, yang berdasarkan teorem penting: jika n ialah nombor komposit, maka sekurang-kurangnya separuh daripada integer positif kurang daripada n memenuhi a^(n-1) mod n != 1. Teras algoritma Miller-Rabin adalah untuk melakukan ujian rawak k untuk integer n tertentu, dan gunakan ini untuk menentukan sama ada n ialah nombor perdana. Biasanya, hanya 15-20 ujian diperlukan untuk mendapatkan keputusan yang lebih tepat.

Berikut ialah kod pelaksanaan Javascript bagi algoritma Miller-Rabin:

// 快速幂算法
function powerMod(a, b, m) {
  let res = 1;

  while (b) {
    if (b & 1) {
      res = (res * a) % m;
    }

    a = (a * a) % m;
    b >>= 1;
  }

  return res;
}

function isPrime(num, k) {
  if (num < 2) {
    return false;
  }

  if (num === 2 || num === 3) {
    return true;
  }

  let d = num - 1;
  let r = 0;

  while (d % 2 === 0) {
    d /= 2;
    r++;
  }

  for (let i = 0; i < k; i++) {
    const a = 2 + Math.floor(Math.random() * (num - 3));
    let x = powerMod(a, d, num);

    if (x === 1 || x === num - 1) {
      continue;
    }

    let flag = false;

    for (let j = 1; j < r; j++) {
      x = (x * x) % num;

      if (x === num - 1) {
        flag = true;
        break;
      }
    }

    if (!flag) {
      return false;
    }
  }

  return true;
}

Di atas ialah tiga kaedah biasa untuk mengira nombor perdana dalam Javascript. Anda boleh memilih kaedah yang sesuai untuk mengira perdana nombor dalam senario aplikasi yang berbeza.

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