回到课程

输出素数

重要程度: 3

大于 1 且不能被除了 1 和它本身以外的任何数整除的整数叫做 prime

换句话说,n > 1 不能被除了 1 和 n 以外的任何数整除,则称为素数。

例如,5 是素数,因为它不能被 23 和 4 整除,会产生余数。

编写可以将 2 到 n 之间的所有素数输出的代码。

n = 10,结果输出 2、3、5、7

P.S. 代码应适用于任何 n,而不是对任何固定值进行硬性调整。

这个任务有很多算法。

我们使用一个嵌套循环:

For each i in the interval {
  check if i has a divisor from 1..i
  if yes => the value is not a prime
  if no => the value is a prime, show it
}

使用标签的代码:

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // for each i...

  for (let j = 2; j < i; j++) { // look for a divisor..
    if (i % j == 0) continue nextPrime; // not a prime, go next i
  }

  alert( i ); // a prime
}

这段代码有很大空间可以优化。例如,我们可以从 2i 的平方根中寻找除数。但无论如何,如果我们想要在很大的时间间隔内实现高效率,我们需要改变方法,依赖高等数学和复杂算法,如[二次筛选] Quadratic sieve, General number field sieve 等等。