Поиск простых чисел на отрезке. Решето Эратосфена

Question

Составлен алгоритм поиска простых чисел при помощи решета Эратосфена от 2 до n.

def erat_sieve(bound):
        if bound < 2:
            return []
        max_ndx = (bound - 1) // 2
        sieve = [True] * (max_ndx + 1)
        #loop up to square root
        for ndx in range(int(bound ** 0.5) // 2):
            # check for prime
            if sieve[ndx]:
                # unmark all odd multiples of the prime
                num = ndx * 2 + 3
                sieve[ndx+num:max_ndx:num] = [False] * ((max_ndx-ndx-num-1)//num + 1)
        # translate into numbers
        return [2] + [ndx * 2 + 3 for ndx in range(max_ndx) if sieve[ndx]]

Нужно составить алгоритм поиска простых чисел от 2^30 до 2^31. Так же существует проблема моего алгоритма. Если я ввожу

erat_sieve(1000000)

то программа работает. Если, например ввожу:

erat_sieve(1073741824)

то выдается ошибка

Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    erat_sieve(1073741824)
  File "C:\Users\Администратор\Desktop\4.py", line 5, in erat_sieve
    sieve = [True] * (max_ndx + 1)
MemoryError

Помогите разобраться в чем ошибка?

Answer 1

Вот так можно уложиться в один гигабайт. Решето работает поверх bytearray (один байт на элемент). Простые числа собираются в array.array('L') (четыре байта на число):

import array
import sys


def erat_sieve(bound):
    if bound < 2:
        return []
    max_ndx = (bound - 1) // 2
    sieve = bytearray(max_ndx + 1)
    #loop up to square root
    for ndx in range(int(bound ** 0.5) // 2):
        # check for prime
        if sieve[ndx] == 0:
            # unmark all odd multiples of the prime
            num = ndx * 2 + 3
            sieve[ndx+num:max_ndx:num] = b'\x01' * ((max_ndx-ndx-num-1)//num + 1)

    sieve.pop()

    a = array.array('L')
    a.append(2)
    a.extend(ndx * 2 + 3 for ndx, v in enumerate(sieve) if v == 0)

    return a


n = int(sys.argv[1])
a = erat_sieve(n)
print(len(a))
print(a[:10])
print(a[-10:])

$ time python erat_sieve.py 1073741824
54400028
array('L', [2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
array('L', [1073741651, 1073741663, 1073741671, 1073741689, 1073741717, 1073741719, 1073741723, 1073741741, 1073741783, 1073741789])

real  0m37.331s
user  0m36.704s
sys   0m0.540s

БЛОГ НА HUSL

Поиск простых чисел на отрезке. Решето Эратосфена

Ответы (1 шт):