sieve of Eratosthenes

sieve.js

function sieve(n) {
  const a = new Int8Array(n + 1);
  const max = Math.floor(Math.sqrt(n));
  let p = 2;

  while (p <= max) {
    for (let i = 2 * p; i <= n; i += p) {
      a[i] = 1;
    }

    while (a[++p]);
  }

  return a.reduce((prev, cur, index) => {
    if (cur === 0 && index >= 2) {
      prev.push(index);
    }

    return prev;
  }, []);
}

function * lazySieve(n) {
  const a = new Int8Array(n + 1);
  const max = Math.floor(Math.sqrt(n));
  let p = 2;

  while (p <= max) {
    for (let i = 2 * p; i <= n; i+=p) {
      a[i] = 1; // 合数记为1
    }

    while (a[++p]); // 找到下一个0，即下一个素数
  }

  for (let i = 2, len = a.length; i < len; i++) {
    if (a[i] === 0) yield i;
  }
}

const siever = lazySieve(20);
for (let primer = siever.next(); !primer.done; primer = siever.next()) {
  console.log("prime:", primer.value);
}