Проблема с проектом Эйлера # 37

Question

Я попробовал несколько способов решить Project Euler # 37 и написал код (который я сделал для проверки фона, и он, кажется, работает отлично), однако в вопросе говорится, что есть только 11 возможных ответовчто мне нужно подвести итог, но я получаю 30. Проблема:

Число 3797 имеет интересное свойство. Будучи простым, можно непрерывно удалять цифры слева направо и оставаться простыми на каждом этапе: 3797, 797, 97 и 7. Аналогично мы можем работать справа налево: 3797, 379, 37 и 3.

Найти сумму только одиннадцати простых чисел, которые можно обрезать слева направо и справа налево.

ПРИМЕЧАНИЕ. 2, 3, 5 и 7 не считаются усеченными простыми числами. .

Таким образом, для каждого простого числа я перебирал диапазон длин его цифр и объединял их для проверки, а затем проверял, была ли тоже цифра простым, и я делал это вперед и назад. ,Если бы все они были простыми числами, я бы добавил к результатам (исходное число) и подвел бы итог.

вот код:

def trunc_primes():
    it_range = range(9, 10000)
    primes = [i for i in it_range if all((i%d)!=0 for d in range(2, i//2))]
    results = []
    counter=0

    for prime in primes:
        splitted = list(str(prime))
        forwards = splitted.copy()
        backwards = splitted[::-1]

        forward_range = range(len(forwards))
        prime_check_dict = {}
        for i in forward_range: prime_check_dict[i]=False

        for fr in forward_range:
            forward = int(''.join(forwards[0+fr:]))
            backward = int(''.join(backwards[0+fr:][::-1])) # reverse back the reversed list

            if all((forward%d)!=0 for d in range(2, forward//2)):
                if all((backward%e)!=0 for e in range(2, backward//2)):
                    prime_check_dict[fr]=True 

        if all(prime_check_dict[i]==True for i in prime_check_dict):
            results.append(prime)
            counter+=1


#here is also some sample background work at the second for loop:

#original:  ['9', '9', '7', '3']
#forward:  9973
#backward:  9973
#original:  ['9', '9', '7', '3']
#forward:  973
#backward:  997
#original:  ['9', '9', '7', '3']
#forward:  73
#backward:  99
#original:  ['9', '9', '7', '3']
#forward:  3
#backward:  9

Возможно, я упускаю незначительную деталь, которая должна быть очевидной илиЯ не понял контекст проблемы

Answer 1

Основной проблемой является испытание в вашей программе является неправильным, так как он принимает 1 и 4, которые, очевидно, не простые числа:

all((i%d)!=0 for d in range(2, i//2))]

С моей точки зрения, еще одна проблема в том, что вы останавливаетесь в 9999Это ограничение либо слишком низкое, если есть решения с 5 цифрами, либо слишком высокое, если вы нашли все 11 решений ранее. (Последнее оказывается верным.)

Верхний предел для делений при тестировании простых чисел равен sqrt (N). Использование N//2 в качестве верхнего предела не является ошибка, но весьма неэффективен для большего числа.

1008 * Мое главное предложение для повышения скорости, чтобы воспользоваться иметь множество небольших простых чисел, уже приданное. Например, при тестировании 3797, вы не должны выполнить тест для производных меньшего числа 379, 37 и 3. Проверки Просто, если они есть (или нет) присутствуют в множестве простых чисел, генерируемых уже на путив 3797