1

Составлен алгоритм поиска простых чисел при помощи решета Эратосфена от 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

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

4
  • вот более продвинутая и более быстрая реализация решета Эратосфена - stackoverflow.com/questions/2068372/… 16 июл 2021 в 10:49
  • 1
    Вы просите выделить массив на полмиллиарда элементов. Вероятно у вас не хватает памяти. 16 июл 2021 в 17:38
  • Ваш скрипт успешно работает потребляя 6.4Gb памяти. 16 июл 2021 в 17:46
  • 1
    Сколько памяти в вашем компьютере? Решение требует много памяти. Сначала аллоцируется примерно bound/2 машинных слов в списке sieve, затем порядка bound/ln(bound) целых чисел в результате. В решете для 1<<30 аллоцируется поряда 550 млн целых чисел, что для 64-х битных машин порядка 6 гб. PS. Я так понимаю, вы позаимствовали решение отсюда.
    – Pak Uula
    18 июл 2021 в 11:13

1 ответ 1

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.