邻家の躺平人对《编程珠玑（续）》的笔记(2)

第一段倒数第二句：

原文：

翻译明显拗口啊，用的google translation么？

第二题的C问中，O(nloglogn)的复杂度可以这么推出：

p = 2;
while (p <= n)
{
	for (i = 2 * p; i <= n; i += p)
	 x[i] = 0;

	do
		p++;
	while (!x[p]);
}

这是经过处理后的代码，主要是便于分析。容易知道，只需要分析x[i] = 0;的运行次数即可。 T(n) = n/2 + n/3 + ... + n/p, 其中p为不大于n最大的素数。然后我们有 T(n) = n(1/2 + 1/3 +..+ 1/p) *fix：吃饭时突然想到刚才右半部分的证明是不对的，特此更正下。 右边的其实是有专业术语的，称之为：素数调和级数，渐进于O(loglogn).欧拉给出了一个下界（非函数增长上的渐进下界，不过可以由此得到Omega）。 http://en.wikipedia.org/wiki/Prime_harmonic_series 如果 log_{a}n = O(logn) => log_{b}n = O(logn)，其中a,b均>1 对于d，目前已知最好的方法是进行素性测试。该测试基于费马小定理，并且可以在现行时间内完成测试，不过没有100%正确的概率。然后可以进行大量独立重复测试，将概率控制在接受范围之内。