Confusing performance results for prime

[Tim Peters]

Here's a cute sieve compromise between speed and memory efficiency, using
one byte per odd number and sticking to core Python:

def numprimes(n):
    "Return the number of primes <= n."

    from array import array

    if n < 2:
        return 0
    if n < 3:
        return 1
    # index 0 <-> 3
    # index 1 <-> 5
    # ...
    # index i <-> 2i+3

    # 2i+3 <= n
    # 2i   <= n-3
    # i    <= (n-3)/2
    i = (n-3) // 2
    size = i+1

    a = array('c', 'p' * size)
    i = 0
    while i < size:
        while a[i] == 'c':
            i += 1
        p = 2*i+3
        sqi = (p*p - 3) >> 1
        if sqi >= size:
            break
        # (p**2 + 2pj - 3) // 2 =
        # (p**2-3 + 2pj) // 2 =
        # (p**2-3)//2 + 2pj//2 =
        # sqi + pj

        # sqi + pj <= size - 1
        # pj <= size - 1 - sqi
        # j <= (size - 1 - sqi) / p
        j = (size - 1 - sqi) // p
        a[sqi : size : p] = array('c', 'c' * (j+1))
        i += 1
    return 1 + a.count('p')