javascript怎么求素数

1. 前言

素数（也称质数）是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。求素数在密码学、数论等领域有着重要的应用。本文将介绍javascript中求素数的方法。

2. 素数的判断方法

判断一个数是否为素数，最简单的方法是试除法。试除法的基本思想是：如果整数n不能被小于n的所有自然数所整除，则n为素数。

2.1 简单的试除法

简单的试除法是通过遍历小于该数的自然数逐一试除，如果有能整除该数的自然数，则该数不为素数。下面是javascript代码实现：

//简单的试除法

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

该方法的时间复杂度为O(n)，效率较低，对于大数会出现超时等问题，因此需要更好的算法。

2.2 筛法

埃拉托斯特尼筛法和欧拉筛法是比较常用的筛法。

2.2.1 埃拉托斯特尼筛法

埃拉托斯特尼筛法的基本思想是：将要筛选的范围内的数从小到大排列，先将2的倍数筛掉，再将3的倍数筛掉……依此类推，直到筛完为止。这样筛掉的数中，只剩下素数。下面是javascript代码实现：

//埃拉托斯特尼筛法

function eratosthenes(n) {
  var isPrime = new Array(n + 1);
  for (var i = 2; i <= n; i++) {
    isPrime[i] = true;
  }
  for (var i = 2; i <= n; i++) {
    if (isPrime[i]) {
      for (var j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime;
}

该方法的时间复杂度为O(n*loglogn)，效率较高，可以处理较大的素数。

2.2.2 欧拉筛法

欧拉筛法是一种优化的筛法，其基本思想是：在埃拉托斯特尼筛法的基础上，去掉了重复标记的数据。下面是javascript代码实现：

//欧拉筛法

function euler(n) {
  var primes = [];
  var isPrime = new Array(n + 1);
  for (var i = 2; i <= n; i++) {
    if (!isPrime[i]) {
      primes.push(i);
    }
    for (var j = 0; j < primes.length && primes[j] * i <= n; j++) {
      isPrime[primes[j] * i] = true;
      if (i % primes[j] == 0) {
        break;
      }
    }
  }
  return primes;
}

该方法的时间复杂度为O(n)~O(n*loglogn)，是目前已知的最优的求素数方法。

3. 总结

本文介绍了javascript中求素数的方法，包括简单的试除法、埃拉托斯特尼筛法和欧拉筛法。其中，欧拉筛法是最优的求素数方法，时间复杂度为O(n)~O(n*loglogn)。我们可以根据具体需求选择不同的算法来求素数。