03.pprofile.out

Benchmark duration: 886.8774709701538 seconds
Command line: ['03.primes-v1.py']
Total duration: 886.878s
File: 03.primes-v1.py
File duration: 886.878s (100.00%)
Line #|      Hits|         Time| Time per hit|      %|Source code
------+----------+-------------+-------------+-------+-----------
     1|         2|  7.10487e-05|  3.55244e-05|  0.00%|import time
     2|         0|            0|            0|  0.00%|
     3|         0|            0|            0|  0.00%|
     4|        41|   0.00029397|     7.17e-06|  0.00%|def primes(n):
     5|        40|  0.000231266|  5.78165e-06|  0.00%|    if n == 2:
     6|         0|            0|            0|  0.00%|        return [2]
     7|        40|  0.000178337|  4.45843e-06|  0.00%|    elif n < 2:
     8|         0|            0|            0|  0.00%|        return []
     9|        40|  0.000188112|  4.70281e-06|  0.00%|    s = []
    10|  39999960|      159.268|  3.98171e-06| 17.96%|    for i in range(3, n+1):
    11|  39999920|      152.924|  3.82312e-06| 17.24%|        if i % 2 != 0:
    12|  19999960|      76.2135|  3.81068e-06|  8.59%|            s.append(i)
    13|        40|   0.00147367|  3.68416e-05|  0.00%|    mroot = n ** 0.5
    14|        40|  0.000319004|   7.9751e-06|  0.00%|    half = (n + 1) / 2 - 1
    15|        40|  0.000220776|  5.51939e-06|  0.00%|    i = 0
    16|        40|  0.000243902|  6.09756e-06|  0.00%|    m = 3
    17|     20000|    0.0777466|  3.88733e-06|  0.01%|    while m <= mroot:
    18|     19960|    0.0774016|  3.87784e-06|  0.01%|        if s[i]:
    19|      6680|    0.0278566|  4.17015e-06|  0.00%|            j = (m * m - 3) / 2
    20|      6680|    0.0275929|  4.13067e-06|  0.00%|            s[j] = 0
    21|  32449400|      114.858|   3.5396e-06| 12.95%|            while j < half:
    22|  32442720|      120.841|  3.72475e-06| 13.63%|                s[j] = 0
    23|  32442720|      114.432|   3.5272e-06| 12.90%|                j += m
    24|     19960|    0.0749919|  3.75711e-06|  0.01%|        i = i + 1
    25|     19960|    0.0765574|  3.83554e-06|  0.01%|        m = 2 * i + 3
    26|        40|  0.000222206|  5.55515e-06|  0.00%|    l = [2]
    27|  20000000|      68.8031|  3.44016e-06|  7.76%|    for x in s:
    28|  19999960|      67.9391|  3.39696e-06|  7.66%|        if x:
    29|   3139880|      10.9989|  3.50295e-06|  1.24%|            l.append(x)
    30|        40|  0.000155687|  3.89218e-06|  0.00%|    return l
    31|         0|            0|            0|  0.00%|
    32|         0|            0|            0|  0.00%|
    33|         2|  8.10623e-06|  4.05312e-06|  0.00%|def benchmark():
    34|         1|  5.00679e-06|  5.00679e-06|  0.00%|  start = time.time()
    35|        41|   0.00101089|   2.4656e-05|  0.00%|  for _ in xrange(40):
    36|        40|     0.232263|   0.00580657|  0.03%|          count = len(primes(1000000))
(call)|        40|      886.644|      22.1661| 99.97%|# 03.primes-v1.py:4 primes
    37|         1|  5.96046e-06|  5.96046e-06|  0.00%|  end = time.time()
    38|         1|  0.000678062|  0.000678062|  0.00%|  print "Benchmark duration: %r seconds" % (end-start)
    39|         0|            0|            0|  0.00%|
    40|         0|            0|            0|  0.00%|
    41|         1|  5.79357e-05|  5.79357e-05|  0.00%|benchmark()
(call)|         1|      886.878|      886.878|100.00%|# 03.primes-v1.py:33 benchmark