好久没写博客了。
这是一个关于寻找质数的故事。
const eratosthenes = function (n: number) {
// Eratosthenes algorithm to find all primes under n
const array = [],
upperLimit = Math.sqrt(n),
output = [];
// Make an array from 2 to (n - 1)
for (let i = 0; i < n; i++) {
array.push(true);
}
// Remove multiples of primes starting from 2, 3, 5,...
for (let i = 2; i <= upperLimit; i++) {
if (array[i]) {
for (let j = i * i; j < n; j += i) {
array[j] = false;
}
}
}
// All array[i] set to true are primes
for (let i = 2; i < n; i++) {
if (array[i]) {
output.push(i);
}
}
return output;
};
完全借鉴于 sieve-of-eratosthenes-algorithm-in-javascript-running-endless-for-large-number
