Ошибка Memory Error

Roodger

Новичок
Пользователь
Авг 20, 2020
15
4
3
Есть такая интересная задачка из проекта Эйлера:

Простое число 41 можно записать в виде суммы шести последовательных простых чисел:
41 = 2 + 3 + 5 + 7 + 11 + 13
Это - самая длинная сумма последовательных простых чисел, в результате которой получается простое число меньше одной сотни.
Самая длинная сумма последовательных простых чисел, в результате которой получается простое число меньше одной тысячи, содержит 21 слагаемое и равна 953.
Какое из простых чисел меньше одного миллиона можно записать в виде суммы наибольшего количества последовательных простых чисел?

Решение вроде простое - надо просто проссумировать все простые числа до тех пор, пока сумма не станет больше или равна миллиону. Затем просто удалять самые маленькие слагаемые до тех пор, пока сумма не станет простым числом.
Но дело в том, что удаление происходит путем итерации, а значит последовательно: первое слагаемое, второе слагаемое и т.д. И в процессе такого удаления можно проскочить одно или несколько простых чисел. И вполне возможно, что при другом варианте удаления слагаемых можно сделать наименьшее количество удалений, что позволит получить наиболее длинный ряд слагаемых
В интернете я как то не нашел удовлетворительного решения или просто не понял их. Там либо вовсе не возвращают слагаемые, либо вовзвращают по одному, что тоже недостаточно. Кстати, пример насчет суммы 21 слагаемого не показательный, так как там как раз удаляются первые три слагаемых и получается решение. Но в случае больших чисел это уже не работает. Например, при простом числе 10 000 у мнея удалилось слагаемое 3, все остальные вроде вернулись на место.
Я написал такой код:
Python:
from itertools import combinations #  модуль всевозможных итераций, берем отиуда функцию комбинирование списка

def sns(): # функция поиска простых чисел в диапазоне
    sn = []
    sn1 = []

    for i in range(3, 40000, 2):
        sn.append(i)
    for p in range(3, int(sn[-1] ** 0.5 + 1), 2):
        for i in range(len(sn)):
            if sn[i] % p == 0 and sn[i] / p != 1:
                sn1.append(sn[i])
    sn.insert(0, 2)
    for i in set(sn1):
        sn.remove(i)

    return sn #функция возвращает список простых чисел в диапазоне (0, 40000)

def summ():
    summ = 0
    s = []
    sn = sns()  # получаем список простых чисел
    s1 = []
    for i in sn:
        if summ < 40000: # здесь мы задаем потолок суммы простых чисел, в данном случае 40000
            summ += i    # это суммирование
            s.append(i)  # это параллельное создание списка слагаемых
        else:
            summ = summ - s[-1] # так как при подсчете проскакивает одно число, которое делает сумму больше 40000,
                                # то мы удаляем его нахрен
            s.pop()             # из списка слагаемых также удаляем последнее число

    for i in range(len(s)):   # начинаем оббегать список слагаемых для его корректировки
        if not sum(s) in sn:  # если сумма чисел не находится в списке простых чисел, то есть не является простым числом
            s1.append(s[0])   # то мы сначала самое маленькое слагаемое закидываем в отдельный список удаленных слагаемых
            s.remove(s[0])    # а затем удаляем его из списка слагаемых

        else:                 # повторяем все это пока не дойдем до суммы, которое само является простым числом
            comb = []

            # так как при удалении слагаемых мы удаляли их по порядку, может получится
            # такая ситуация, что при возврате какой то комбинации удаленных слагаемых
            # может получится сумма - простое число. в котором количество слагаемых больше, чем в  текущей сумме
            # поэтому мы начнем возвращать удаленные слагаемые во всевозможных комбинациях для того, чтобы
            # удостовериться, что больше никакой суммы в виде простого числа не получится

            for i in range(1, len(s1) + 1):            # идем по списку удаленных слагаемых
                comb.append(list(combinations(s1, i))) # получаем все возможные комбинации слагаемых
                # в результате мы получаем список кортежей с различными вариантами комбинаций удаленных сдагаемых
            res = []

            for i in range(len(comb)):                 # начинаем проходить по каждему кортежу отдельно
               for j in range(len(comb[i])):           # и в каждом кортеже по каждому элементу
                   if sum(s) + sum(comb[i][j]) in sn:  # к текущей сумме прибавляем сумму текущей комбинации удаленных слагаемых
                                                       # и проверяем получившуюся сумму на простое число
                       res = []                        # если да, то мы создаем пустой список
                       res = s + list(comb[i][j])      # и помещаем туда все текущие слагаемые и удачный вариант
                                                       # комбинации удаленных слагаемых

            if sum(res) == 0:           # это проверка на случай, если удачных комбинаций не окажется
                print (sum(s), len(s))  # тогда мы просто возвращаемся к существующей сумме

            else:
                print(sum(res), len(res)) #Печатаем сумму и количество слагаемых
            break

summ()

Я постарался в комментариях расписать его. чтобы был понятен ход моих мыслей
Однако вот это строка:
Python:
 comb.append(list(combinations(s1, i)))
при значениях в районе 50 000 уже вызывает переполнение памяти.
Хотел спросить, есть ли возможность обойтись без такого перебора слагаемых?
 

Форум IT Специалистов