В общем есть задача
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 тоже видимо не стоит, итак перебор :-)
