python执行效率疑问

Question

打印1-200000以内素数，我测试了两段代码。 第一种采用函数调用的方式花了1.87s，第二种把函数体写到循环体里面执行，反而花了2.25s。这是为什么呢？

（1）

def isPrime(n):     
    if n <= 1:     
        return False
    if n == 2:     
        return True
    if n % 2 == 0:     
        return False
    i = 3
    while i * i <= n:     
        if n % i == 0:     
            return False
        i += 2
    return True

for n in range(1, 200000):
    if isPrime(n):     
         print n  

（2）

for n in range(1, 200000):
    if n <= 1:     
        continue
    if n == 2:
        print n
        continue
    if n % 2 == 0:     
        continue
    i = 3
    flag = True
    while i * i <= n:     
        if n % i == 0: 
            flag = False
            break
        i += 2
    if flag:
        print n

Answer 1

因为第二种算法是错的，多打印出了许多东西。break 之后合数还是被打印出来了。

PS: 利用 Python 3.2+ 的 functools.lru_cache，可以轻松实现更好的算法。

---

来，修正后的第二种算法为什么还是比较慢：

>>> time python2 a.py > /dev/null
python2 a.py > /dev/null  1.15s user 0.01s system 99% cpu 1.165 total
>>> time python2 b.py > /dev/null
python2 b.py > /dev/null  1.66s user 0.01s system 99% cpu 1.677 total
>>> time python2 c.py > /dev/null
python2 c.py > /dev/null  1.03s user 0.00s system 99% cpu 1.035 total
>>> time python2 a.py > /dev/null
python2 a.py > /dev/null  1.06s user 0.02s system 98% cpu 1.092 total
>>> time python2 b.py > /dev/null
python2 b.py > /dev/null  1.70s user 0.02s system 99% cpu 1.721 total
>>> time python2 c.py > /dev/null
python2 c.py > /dev/null  1.05s user 0.00s system 99% cpu 1.058 total

第三种算法如下：

def t():
  for n in range(1, 200000):
      if n <= 1:
          continue
      if n == 2:
          print n
          continue
      if n % 2 == 0:
          continue
      i = 3
      flag = True
      while i * i <= n:
          if n % i == 0:
              flag = False
              break
          i += 2
      if flag:
          print n

t()

查找全局变量比查找局部变量慢。

Answer 2

我在这里凑个热闹，python 写的打印素数，没别的，只是速度很快。

3.py 是上面@依云 写的 4.py 是我的：

import math

N = 200000
M = int(math.sqrt(N));
a = [1]*N

for i in range(3, M, 2):
    for j in range(i+i, N, i):
        a[j]=0

print 2
for i in range(3, N, 2):
    if a[i] == 1:
        print i

算法是逆向思考，从3开始，3的倍数肯定都不是素数，全部排除，5也同理。。最后输出剩下的就好了。

严格的说 M 应该是int(math.sqrt(N)) + 1吧

Answer 3

找素数最少判断个数应该采用的策略是，6N+1和6N-1应该比单独判断奇数要少1/3时间。