exibite777
@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 тоже видимо не стоит, итак перебор :-)
  • Вопрос задан
  • 504 просмотра
Решения вопроса 1
longclaps
@longclaps
Головой подумай
[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@Karpion
По моим ощущениям - Вы считаете "1" простым числом, а авторы задачи думают иначе.

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

Upd: Открыл ветку комментариев выше - оказывается, там это уже есть.
Ответ написан
@kotam
Та же история была, перевёл "1" в "непростые" и ответ сошёлся! Но "1" составная, что ли, или сама по себе "1"?
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
МТС Москва
от 150 000 до 250 000 ₽
Wunder Fund Москва
от 120 000 до 150 000 ₽
04 июн. 2020, в 03:14
1000 руб./за проект
04 июн. 2020, в 00:28
20000 руб./за проект
03 июн. 2020, в 23:41
75000 руб./за проект