算法阅读笔记

Sieve of Eratosthenes

The Sieve of Eratosthenes finds all primes up to n by marking multiples of each discovered prime as composite.

类型算法分类Math深度初级典型复杂度O(n log log n)

简短面试回答

先从这个心智模型开始

The Sieve of Eratosthenes finds all primes up to n by marking multiples of each discovered prime as composite.

简单解释

它如何工作，不堆砌不必要的术语

Start with all candidates marked prime.

For each prime p up to √n, mark multiples starting at p²; smaller multiples were already handled.

执行过程

把算法读成一连串决策

State the mathematical identity/property.

Choose numeric representation and constraints.

Translate the property into an iterative/recursive computation and analyze precision.

记住一个小例子

Read a tiny input by hand and write down the state after every important operation. For Sieve of Eratosthenes, the goal is to make the invariant visible rather than to memorize code.

易读的 JavaScript 实现JavaScript

function primesUpTo(n) {
  const prime = Array(n + 1).fill(true);
  prime[0] = prime[1] = false;
  for (let p = 2; p * p <= n; p++) {
    if (!prime[p]) continue;
    for (let x = p * p; x <= n; x += p) prime[x] = false;
  }
  return prime.flatMap((isPrime, i) => isPrime ? [i] : []);
}

如何阅读这段代码

不要死记语法。跟踪每一行中发生变化的状态，并把它与上面描述的不变量联系起来。

复杂度

O(n log log n)

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

何时使用

适用场景

Use the direct mathematical property when it removes unnecessary brute force.

常见错误

通常哪里会出错

Ignoring floating-point precision or integer range.
Using a formula outside its valid assumptions.

面试中如何解释

专业回答结构

Mention O(n log log n) time and O(n) space, and explain why marking can start from p².

问题→核心思路→不变量 / 状态→Big-O→权衡

快速面试检查

What problem does Sieve of Eratosthenes solve?

The Sieve of Eratosthenes finds all primes up to n by marking multiples of each discovered prime as composite.

关于复杂度应该提到什么？

Its typical cost here is O(n log log n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

最常见的错误是什么？

Ignoring floating-point precision or integer range.

继续阅读Number theoryNumerical precisionRecurrences

function primesUpTo(n) { const prime = Array(n + 1).fill(true); prime[0] = prime[1] = false; for (let p = 2; p * p <= n; p++) { if (!prime[p]) continue; for (let x = p * p; x <= n; x += p) prime[x] = false; } return prime.flatMap((isPrime, i) => isPrime ? [i] : []); }