返回课程

输出素数

重要性:3

大于 1 的整数被称为素数,如果它不能被除以 1 和自身以外的任何数,并且没有余数。

换句话说,n > 1 是一个素数,如果它不能被除以 1n 以外的任何数,并且没有余数。

例如,5 是一个质数,因为它不能被 234 整除。

编写代码,输出从 2n 区间内的质数。

对于 n = 10,结果将是 2,3,5,7

注意:代码应该适用于任何 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 的平方根寻找除数。但无论如何,如果我们想要对大型区间进行真正有效的计算,我们需要改变方法,并依赖于高级数学和复杂算法,例如 二次筛法一般数域筛法 等。