JavaScript如何求数组中的质数

# JavaScript如何求数组中的质数

## 引言

在编程中，处理数组和数学计算是常见的任务。质数（只能被1和自身整除的自然数）的判断与筛选在算法题、密码学等领域有广泛应用。本文将详细介绍如何使用JavaScript从数组中筛选出质数，包括基础实现、性能优化和实际应用示例。

---

## 一、质数的定义与判断方法

### 1.1 质数的数学定义
质数是指大于1的自然数，且**只能被1和它本身整除**。例如：2, 3, 5, 7等。

### 1.2 判断质数的算法
常见方法有：
- **试除法**：检查从2到√n的所有整数是否能整除n。
- **埃拉托斯特尼筛法**：适合筛选一定范围内的质数（但对单个数的判断效率较低）。

---

## 二、JavaScript实现数组质数筛选

### 2.1 基础实现：试除法
```javascript
function isPrime(num) {
  if (num <= 1) return false;
  if (num === 2) return true;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

function filterPrimes(arr) {
  return arr.filter(num => isPrime(num));
}

// 示例
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(filterPrimes(numbers)); // 输出 [2, 3, 5, 7]

2.2 优化：跳过偶数

除2外，所有偶数都不是质数，可以提前排除：

function isPrimeOptimized(num) {
  if (num <= 1) return false;
  if (num === 2) return true;
  if (num % 2 === 0) return false;
  for (let i = 3; i <= Math.sqrt(num); i += 2) {
    if (num % i === 0) return false;
  }
  return true;
}

三、性能对比与边界情况

3.1 时间复杂度分析

• 试除法：O(√n) 每次判断。
• 优化版：减少约一半的循环次数。

3.2 边界情况处理

• 负数和非整数：直接返回false。
• 大数问题：JavaScript的数值精度限制可能导致误差。

四、实际应用示例

4.1 统计质数数量

const countPrimes = (arr) => filterPrimes(arr).length;
console.log(countPrimes([11, 12, 13, 14, 15])); // 输出 2

4.2 找出范围内的质数

结合Array.from生成数组：

function generatePrimesInRange(start, end) {
  return Array.from({ length: end - start + 1 }, (_, i) => start + i)
    .filter(num => isPrime(num));
}
console.log(generatePrimesInRange(10, 20)); // 输出 [11, 13, 17, 19]

五、扩展：使用Web Worker优化大数组

对于超大型数组（如1e6个元素），可以用Web Worker避免阻塞主线程：

// worker.js
self.onmessage = function(e) {
  const primes = e.data.filter(num => isPrime(num));
  self.postMessage(primes);
};

// 主线程
const worker = new Worker('worker.js');
worker.postMessage(largeArray);
worker.onmessage = function(e) {
  console.log('筛选结果:', e.data);
};

六、总结

1. 核心步骤：遍历数组，用试除法判断每个元素是否为质数。
2. 优化方向：跳过偶数、减少循环次数、并行处理。
3. 应用场景：数据清洗、算法题、加密算法等。

通过本文的代码示例和优化策略，你可以高效地在JavaScript中处理质数筛选问题。

附录：完整代码

// 最终优化版
const isPrime = (num) => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 === 0 || num % 3 === 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i === 0 || num % (i + 2) === 0) return false;
  }
  return true;
};

const filterPrimes = (arr) => arr.filter(isPrime);

”`