leetcode 寻找素数 python

2018年3月30日,做了一早上,想了好久,在提示的帮助下,终于做出这道题,本文给出自己的算法改进过程

题目非常简单:

给定一个数 n , 找到小于 n 的所有素数的数目

Count the number of prime numbers less than a non-negative number, n.

1. 思路1

从素数的定义出发: 如果一个数只能被 1 和它本身整除,那么这个数就是素数

按照这个思路,我们要判断小于 n 的每个数 k ,该数要进行 (k-2) 次整除判断,时间复杂度是 \(\mathcal {O}(n^2)\)

在 leetcode 测试,

  • n = 20000, 所需时间为 1548 ms
  • n = 50000, 超时

2. 思路2

如果一个数 n 不是素数,即 n 为合数,那么 n 可以表示为 \(n = p \times q\), 其中 \(p, q \in N, p, q \lt n\) ,如果再继续分析,显然 \(p, q\) 不可能同时大于 \(\sqrt {n}\), 否则 \(p \times q \gt \sqrt {n} \times \sqrt {n} = n\).

由此可以说明,我们只要判断 \(n\) 是否可以被 \([2, \sqrt {n}]\) 之间的所有整数整除,就可以了

上面的代码改进如下:

在 leetcode 测试,

  • n = 20000, 所需时间为 68 ms
  • n = 50000, 所需时间为 164 ms
  • n = 500000, 超时

3. 思路3

利用结论:任何一个合数都可以分解为若干个素数相乘.

我们可以额外加一个 list 来存放素数数组,然后只要判断是否可以被小于 \(\sqrt {n}\) 的素数整除就可以了

代码如下:

在 leetcode 测试,

  • n = 50000, 所需时间为 136 ms
  • n = 400000, 所需时间为 1616 ms
  • n = 500000, 仍然超时

4. 思路四

前面都是增量法,即由小到大,逐点判断是否为素数。

我们换个思路,先建立一个长度为 \(n\) 的数组

如果我们知道一个数是素数,那么在数组中删除它的所有倍数的数?在剩下的数中,最小的数一定是素数,并循环进行下去。

这个方法就是 Sieve of Eratosthenes

请注意,具体如何实施删除操作呢 ?

我开始想用数组 list(range(n)) ,然后每次 pop 出素数的倍数,结果报告索引越界了。自己想了想,哦,如果用 pop , 数组索引和长度均会变化,索引值自然无法比较了

于是,自然想到 list 中存放的是索引对应的状态 (0 – 合数, 1– 素数),如果它是某个素数的倍数,将对应的值标记为 0,表示 它是合数

代码如下:

请注意上面对 素数倍数索引对应的值均赋为 0 使用的技巧

list_n[2*k:n:k] = [0]*((n-2*k-1)//k + 1)

在 leetcode 测试,

  • n = 50000, 所需时间为 48 ms
  • n = 400000, 所需时间为 136 ms
  • n = 800000, 所需时间为 124 ms

5. 思路5

在看动图的时候,不知道你有没有注意到一点,赋值操作是有冗余的,比如索引值为 10, \(10 = 2 \times 5\) ,因此它会在 2 和 5 的倍数时,分别被两次赋值为 0。

如何避免这一点 ?

修改赋值索引的起点 !!!! 从索引值为素数的平方开始赋值,仔细想想吧.

在 leetcode 测试:

  • n = 400000, 所需时间为 76 ms
  • n = 800000, 所需时间为 120 ms

最后在提出一点改进的地方,既然索引起点是 素数的平方,自然上面的 k 的范围就不用是 range(n) ,小于等于 sqrt(n) 就好了

最终版本:

在 leetcode 测试:

  • n = 800000, 所需时间为 120 ms

发表评论

电子邮件地址不会被公开。 必填项已用*标注