素数筛法的复杂度

zhiqiang三月 30, 2008 计算机科学

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;
  return p;
}

此算法复杂度实际为 $O(\sum_{p<n}n/p) = O(n\log\log n)$ 。在可以测试的范围内，的确是接近线形的，虽然实际上不是。下面是如何估计 $\sum\frac1p$ :

$\begin{eqnarray}\log\log\infty&=&\ln \left( \sum_{n=1}^\infty \frac{1}{n}\right) = \ln \left( \prod_{p} \frac{1}{1-p^{-1}}\right) = \sum_{p} \ln \left( \frac{1}{1-p^{-1}}\right) = \sum_{p} - \ln(1-p^{-1}) \\&=&\sum_{p} \left( \frac{1}{p} + \frac{1}{2p^2} + \frac{1}{3p^3} + \cdots \right) = \left( \sum_{p}\frac{1}{p} \right) + \sum_{p} \frac{1}{p^2} \left( \frac{1}{2} + \frac{1}{3p} + \frac{1}{4p^2} + \cdots \right)\\&=& \sum_{p} \left( \frac{1}{p} + \frac{1}{2p^2} + \frac{1}{3p^3} + \cdots \right) = \left( \sum_{p}\frac{1}{p} \right) + \sum_{p} \frac{1}{p^2} \left( \frac{1}{2} + \frac{1}{3p} + \frac{1}{4p^2} + \cdots \right)\\&<& \left( \sum_{p}\frac{1}{p} \right) + \sum_{p} \frac{1}{p^2} \left( 1 + \frac{1}{p} + \frac{1}{p^2} + \cdots \right) = \left( \sum_{p} \frac{1}{p} \right) + \left( \sum_{p} \frac{1}{p(p-1)} \right)\\&=& \left( \sum_{p} \frac{1}{p} \right) + C\end{eqnarray}$

更精确的，

$\sum_{p<n}\frac1p = \log\log n+\Theta(1)$

注意此估计可直接得出素数有无穷多个。

关于复杂度, 复杂性, 算法, 素数 »

图同构问题属于P？更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。提交论文到arxiv不需要审阅...
编程的核心是数据结构，而不是算法 Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学: 你无法断定程序会在什么地方耗费运...
Perfect Shuffle的算法珍爱生命，远离政治。我们继续讨论算法。 2008/04/01补充：此算法有重大缺陷。详情请见留言部分。一年前，我们讨论过一个算法问题，perfect shuffle，...
有序矩阵的中位数算法给定$$n\times n$$的实数矩阵，每行和每列都是递增的，求这$$n^2$$个数的中位数。使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数...
理论计算机初步：算法和计算模型下面是wikipedia上算法的定义：算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算...
求平方根倒数的算法下面这个求$$1/\sqrt{x}$$的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。 float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x...
一个算法面试题 & 面试题库一个面试题，号称是微软的输入$$a_1, a_2, ..., a_n, b_1, b_2, ..., b_n$$，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为$$a_1, b_1, ..., a_n, b_n$$。刚一...
一个简单图的三染色算法问题注: 这个问题来自China Theory Week 2008的Open Problems Session。我们知道在数学里证明一个东西的存在性的时候，有时候只证明了“存在性”，而且在证明过程...
魔方里的数学今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学...
PCP - Probabilistic Checkable Proof PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一，它给了NP问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP...

9条留言 -> 跳到留言表格

At 2008.03.31 10:05, sog.white said:

求素数有没有效率比较高的算法？

上次我面试，还遇到让我写这个算法，我想了半天，最后还是写了这个反复相乘的法子。

最后估计了一下这个的时间复杂性，感到很没有面子。

[Reply]
At 2008.03.31 12:36, Cody said:

我土。最后一句是为啥？由这个算法复杂度怎么得出素数有无穷多个？

[Reply]
- At 2008.03.31 15:56, sog.white said:
  
  It's just joke
  
  倒置举证法
  
  [Reply]
At 2008.03.31 19:47, fcicq said:

for (int i = 2; i < n; i++)
替换为
s = sqrt(n) + 1;
for (int i = 2; i < s; i++)

想想为什么?

[Reply]
At 2008.03.31 20:04, zhiqiang said:

@sog white: 如果需要求出小于n的所有素数，这个算法在数量级上应该无法突破了，但细节上还可以优化很多，就如fcicq所说，加快个一两倍的速度都是可能的。

@cody: 素数的倒数和都是无穷大了，素数当然更是无穷多个了。

[Reply]
At 2008.04.01 14:46, rex said:

恰巧，我刚写了一篇博客文章，分析“使用正则式运行质数、合数判定的内幕”。其中遇到一个问题，即，设有m,n均为非0自然数，是否能够证明，(m+1)*(n+1)全等于所有合数的集合？

原文链接在此。

[Reply]
At 2008.04.05 02:27, rmq said:

for (int j = 2*i; j < n; j+=i)
是不是应该
for (int j = i*i; j < n; j+=i)

[Reply]
At 2009.04.27 20:03, 5l2 said:

for (int j = 2*i; j < n; j+=i)
改成
for (int j = i*i; j < n; j+=i)
会影响时间复杂度么？

[Reply]
At 2009.05.22 16:57, E剑仙 said:

最高有O(n/logn)的筛法

[Reply]

« 如何和谐议政

Perfect Shuffle的算法 »

素数筛法的复杂度

阅微堂