How to calculate prime numbers in javascript

Prime numbers refer to positive integers that can only be divided by 1 and themselves. They are an important concept in mathematics and are widely used in computer science. In Javascript, we can use the following methods to calculate prime numbers.

1. Violent enumeration method

The violent enumeration method is a simple and direct method of calculating prime numbers. We can start from 2 and traverse to n-1, and determine whether each integer can divide n. If there is an integer m that divides n, then n is not prime. If n is not divisible by every integer m, then n is a prime number.

The following is the Javascript implementation code of the violent enumeration method:

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

2. Sieve of Eratosthenes

Sieve of Eratosthenes is a faster way to calculate prime numbers method. Its basic idea is to first arrange all positive integers in order, and then filter out the numbers that can be divided by 2 starting from 2, then filter out the numbers that can be divided by 3, then filter out the numbers that can be divided by 5, and so on. , until no more prime numbers can be filtered out.

The following is the Javascript implementation code of 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. Miller-Rabin algorithm

Miller-Rabin algorithm is a probabilistic prime number Test algorithm, which is based on an important theorem: if n is a composite number, then at least half of the positive integers a less than n satisfy a^(n-1) mod n != 1. The core of the Miller-Rabin algorithm is to perform k random tests for a given integer n, and use this to determine whether n is a prime number. Normally, only 15-20 tests are needed to obtain more accurate results.

The following is the Javascript implementation code of the Miller-Rabin algorithm:

// 快速幂算法
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;
}

The above are the three common methods for calculating prime numbers in Javascript. You can choose a suitable method to calculate prime numbers in different application scenarios.

The above is the detailed content of How to calculate prime numbers in javascript. For more information, please follow other related articles on the PHP Chinese website!