@exibite777

Проект Эйлера. Задача #37. Не понимаю постановку вопроса?

В общем есть задача euler.jakumo.org/problems/view/37.html
https://projecteuler.net/problem=37

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

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

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


Решение на Python3 выглядит следующим образом:

n = 1000000 
a = list(range(n+1))
a[1] = 0; lst = []
i = 2
while i <= n:
    if a[i] != 0:
        lst.append(a[i])
        for j in range(i, n+1, i):
            a[j] = 0
    i += 1
    
def isSimple(num):
    if num<1 or num in [4,6,9]: return False
    for i in range(2,ceil(sqrt(num))):
        if num%i==0: return False
    return True

def trunc_combinations(s1):
    lst=[s1]
    for i in range(1,len(s1)):
        lst.append(s1[i:])
        lst.append(s1[:i])
    return lst

def isTruncSimple(num):
    combinations=trunc_combinations(str(num))
    for combination in combinations:
        if not isSimple(int(combination)):
            return False
    return True
    
lch=[]
for num in lst[4:]:
    if isTruncSimple(num):
        lch.append(num)
print(lch)
print(sum(lch))
    
print(datetime.now()-start)


Решение судя по всему работает. Не вдаюсь в описание алгоритма, кто разбирается в Python3, тот поймет. Почему именно так, а не эдак тоже не уточняю, часть решений сделано для ускорения работы алгоритма. В общем выдает оно вот такой результат
[11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 197, 311, 313, 317, 373, 797, 1373, 1997, 3137, 3797, 7331, 73331, 739397]
833554

Вопрос: о каких 11 элементах идет речь в задаче? Что именно суммировать,? Естественно ответ не принимает. Увеличивать счетчик выше 1000000 тоже видимо не стоит, итак перебор :-)
  • Вопрос задан
  • 341 просмотр
Решения вопроса 1
longclaps
@longclaps
Головой подумай
[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@Karpion
По моим ощущениям - Вы считаете "1" простым числом, а авторы задачи думают иначе.

Вообще, считать ли "1" простым числом - зависит от волевого решения. Многие теоремы на тему простых чисел - не срабатывает на единице, поэтому её исключили из комсомола из списка простых чисел.

Upd: Открыл ветку комментариев выше - оказывается, там это уже есть.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы