Javascript 质数生成器

Question

我正在尝试生成小于20的前几个质数（根据我的有限知识，这是我唯一知道如何做到的方式）：

let arr = [];

for (let x = 3; x <= 20; x++) {
  for (let i = 20; i > 0; i--) {
    if (x % i !== i) {
      arr.push(x)
    }
  }
  console.log(arr)
}

我想预先说明，虽然有更高效的方法可用，但我正在尝试从头开始做事并学习更高效的方法，而不是让别人告诉我。

代码的意图：

1. 一个外部循环，从3开始，到20结束，增量为1
2. 一个内部循环，从20开始，到0结束，减量为1。
3. 内部循环中的条件：如果数字x对i的范围取模并返回i，则它不是素数。

示例：

7 is prime.

7 % 7 = 0
7 % 6 = 1
7 % 5 = 2
7 % 4 = 3
7 % 3 = 4
7 % 2 = 5
7 % 1 = 6

而

6 is not prime

6 % 6 = 0
6 % 5 = 1
6 % 4 = 2
6 % 3 = 3    <=== because of this
6 % 2 = 4
6 % 1 = 5

输出是从3到20的数字范围的20个倍数。即， 3,3,3,3,3,........20,20,20.....

- Raboush2

---

用 9 测试你的方法。 - Pointy

不需要逐一增加1，您可以逐一增加2（偶数不是质数）。 - depperm

6%3 = 0，而不是3。其他的模数也是关闭的。 - President James K. Polk

并且使代码更加高效 :o - Raboush2

是的，我正在立即修复它，我对Modulu的理解有误。 - Raboush2

Answer 1

由于OP更注重清晰度而非效率，有一个简单的观察可以大幅减少搜索量且不会增加太多复杂性：非质数必有一个质因子，因此我们可以将可被整除性检查限制在已找到较小质数范围内。

简而言之...

let arr = [];

for (let x = 3; x <= 20; x++) {
  // check only the previously found primes
  let isPrime = true;
  for (let i = 0; i < arr.length; i++) {
    if (x % arr[i] === 0) {
      isPrime = false;
      break;
    }
  }
  if (isPrime) arr.push(x)
}

console.log(arr)

简洁地写...

let primes = [];

for (let x = 3; x <= 20; x++) {
  if (primes.every(prime => x % prime !== 0)) primes.push(x)
}

console.log(primes)

- danh

---

你有尝试过代码高尔夫吗？ - JosephDoggie

Answer 2

所以这个逻辑有一些缺陷。有几种方法可以优化代码并修复逻辑。

• 外循环可以每次增加2（偶数不是素数）
• 内循环不需要从比x更大的数字开始，而是从x-1开始并到1结束
• 添加一个标志（np非素数）来跟踪数字是否为素数
  • 如果x％i等于0，则标记np并停止循环（如果某个数字（x）可被较小的数字（i）整除，则它不是素数）
  • 只有在！np（或素数）时才添加x
  • 为每个x重置标志

let arr = [];
let np=false
for (let x = 3; x <= 20; x+=2) {
  np=false
  for (let i = x-1; i > 1; i--) {
    if (x % i === 0) {
      np=true
      break
    }
  }
  if(!np){
    arr.push(x)
  }
}
console.log(arr)

- depperm