What is the algorithm for finding prime numbers in JavaScript?

Prime numbers refer to positive integers that can only be divisible by 1 and themselves. The algorithm for finding prime numbers is a very basic and important problem in computer science. It can be applied to many fields, such as encryption, data compression, etc.

In JavaScript, it is very simple to implement the algorithm for finding prime numbers. Below I will introduce two methods:

1. prime number judgment method

This method is the most basic method for finding prime numbers. Its principle is to judge whether a positive integer can only Divisible by 1 and itself. The specific implementation method is as follows:

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是素数
}

This function receives a positive integer n as a parameter. If n is a prime number, it returns true, otherwise it returns false. Its time complexity is O(n), which is not optimal. If you need to judge a large number of prime numbers, it is recommended to use the Sieve of Eratosthenes introduced below.

2. Sieve of Eratosthenes

This method removes composite numbers through a series of sieves, leaving only prime numbers. The specific implementation method is as follows:

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;
}

This function receives a positive integer n as a parameter and returns an array of prime numbers less than or equal to n. Its time complexity is O(n log log n), which is faster than the prime number judgment method.

Conclusion

The above are two methods of finding prime numbers in JavaScript. Although the implementation is simple, it is very practical. If you are interested in prime numbers, you can try to optimize these two methods to make them faster and more efficient.

The above is the detailed content of What is the algorithm for finding prime numbers in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!