PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一，它给了NP问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP介绍。
作者：yijia
我们可以从最基本的NP开始。一般NP的定义是基于nondeterministic Turing machine，但我们也可以用类似于Interactive Proof的系统来刻画：
一个语言是在NP内当且仅当存在一个多项式时间的算法  (i.e., prover...

Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。
所谓素数筛法就是那个求小于n的所有素数最简单的算法：
bool* prime(int n) {
bool *p = new bool[n];
memset(p, 0, sizeof p);
for (int i = 2; i < n; i++)
if (!p[i])
for (int j = 2*i; j < n; j+=i)
p[j] = true;
[...]