输出素数
重要性:3
大于 1
的整数被称为素数,如果它不能被除以 1
和自身以外的任何数,并且没有余数。
换句话说,n > 1
是一个素数,如果它不能被除以 1
和 n
以外的任何数,并且没有余数。
例如,5
是一个质数,因为它不能被 2
、3
和 4
整除。
编写代码,输出从 2
到 n
区间内的质数。
对于 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
}
还有很多优化空间。例如,我们可以从 2
到 i
的平方根寻找除数。但无论如何,如果我们想要对大型区间进行真正有效的计算,我们需要改变方法,并依赖于高级数学和复杂算法,例如 二次筛法、一般数域筛法 等。