Задача #1356

Делители и маски

Сложнее ЕГЭ

(С. Чайкин) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10⁸, найдите 5 наибольших простых чисел, для которых $n$ $ соответствует маске 5*3?9*1.

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

Примечание: с помощью $n $$ обозначим сумму всех простых чисел, не первышающих $n$ .

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

45313699

2736056

45313391

2736032

45312307

2735966

45311971

2735944

45311603

2735922


from fnmatch import *

# найдем все простые числа, не превышающие 10^8
# для этого воспользуемся решетом Эратосфена
n = 10**8
p = [0, 0, 1] + [x % 2 for x in range(3, n+1)]

for d in range(3, int(n ** 0.5)+1):
    if p[d] != 0:
        for j in range(d*d, n+1, d):
            p[j] = 0

# для каждого простого числа посчитаем сумму n$
# применим префиксные суммы для этого
pr = [(0, 0, 0)]

for i in range(1, n+1):
    if p[i]:
        pr += [(i, pr[-1][1] + i, pr[-1][2] + 1)]

# разворачиваем наш список и выводим первые 5 подходящих чисел
count = 0

for n, s, c in pr[::-1]:
    if fnmatch(str(s), '5*3?9*1'):
        print(n, c)
        count += 1

        # если кол-во чисел равно 5
        if count == 5:
            # выходим из цикла
            break

Номер

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

0/158

решено

Номер