Сделать системный вызов в Python

Я знаю, что конкурс закрыт на несколько лет. ...

Тем не менее это мое предложение для чистого простого сита python, основанного на исключении кратных 2, 3 и 5 с помощью соответствующих шагов при обработке сита вперёд. Тем не менее, это на самом деле медленнее для N & lt; 10 ^ 9, чем @Robert William Hanks превосходные решения rwh_primes2 и rwh_primes1. С помощью массива ctypes.c_ushort выше 1.5 * 10 ^ 8 он каким-то образом адаптируется к ограничениям памяти.

10 ^ 6

$ python -mtimeit -s "import primeSieveSpeedComp" " PrimeSieveSpeedComp.primeSieveSeq (1000000) "10 циклов, лучше всего 3: 46,7 мсек за цикл

для сравнения: $ python -mtimeit -s" import primeSieveSpeedComp "" primeSieveSpeedComp.rwh_primes1 (1000000) "10 петли, лучше всего 3: 43,2 мсек за цикл для сравнения: $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (1000000)" 10 циклов, лучше всего 3: 34,5 мсек за цикл

10 ^ 7

$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (10000000)" 10 циклов, лучше всего 3: 530 мсек за цикл

для сравнения: $ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (10000000)" 10 циклов, лучше всего 3: 494 мсек за цикл для сравнения: $ python -m timeit -s "import primeSieveSpeedComp" " primeSieveSpeedComp.rwh_primes2 (+100000 00) «10 циклов, лучше всего 3: 375 мсек за цикл

10 ^ 8

$ python -mtimeit -s" import primeSieveSpeedComp "" primeSieveSpeedComp.primeSieveSeq ( 100000000) «10 циклов, лучше всего 3: 5,55 сек за цикл

для сравнения: $ python -mtimeit -s" import primeSieveSpeedComp "" primeSieveSpeedComp.rwh_primes1 (100000000) "10 циклов, лучший из 3: 5,33 с за цикл для сравнения: $ python -m timeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (100000000)" 10 циклов, лучше всего 3: 3,95 с за цикл

10 ^ 9

$ python -mtimeit -s "import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (1000000000)" 10 циклов, лучше всего 3: 61,2 сек за цикл

to Сравнение: $ python -mtimeit -n 3 -s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (1000000000)" 3 петли, лучше всего 3: 97,8 сек за цикл

для сравнения: $ python -m timeit - s "import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (1000000000)" 10 петель, лучше всего 3: 41,9 сек за цикл

Вы можете скопировать код ниже в ubuntus primeSieveSpeedComp, чтобы просмотреть эти тесты.

def primeSieveSeq(MAX_Int):
    if MAX_Int > 5*10**8:
        import ctypes
        int16Array = ctypes.c_ushort * (MAX_Int >> 1)
        sieve = int16Array()
        #print 'uses ctypes "unsigned short int Array"'
    else:
        sieve = (MAX_Int >> 1) * [False]
        #print 'uses python list() of long long int'
    if MAX_Int < 10**8:
        sieve[4::3] = [True]*((MAX_Int - 8)/6+1)
        sieve[12::5] = [True]*((MAX_Int - 24)/10+1)
    r = [2, 3, 5]
    n = 0
    for i in xrange(int(MAX_Int**0.5)/30+1):
        n += 3
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 3
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
    if MAX_Int < 10**8:
        return [2, 3, 5]+[(p << 1) + 1 for p in [n for n in xrange(3, MAX_Int >> 1) if not sieve[n]]]
    n = n >> 1
    try:
        for i in xrange((MAX_Int-2*n)/30 + 1):
            n += 3
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 3
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
    except:
        pass
    return r