Дана последовательность натуральных чисел и нулей. Рассматриваются все её непрерывные подпоследовательности, в которых количество простых чисел кратно 
. Найдите наибольшую сумму такой последовательности.
Входные данные. Даны два входных файла(файл А_5 и файл В_5), каждый из которых содержит в первой строке количество чисел 
(
). Каждая из следующих 
строк файлов содержит одно натуральное число, не превышающее 
.
В ответ запишите два числа через пробел — сначала ответ для файла А, затем для файла Б.
Решение 1 (неэффективное)
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
cnt, sum = 0, 0
for j in range(i, n):
sum += a[j]
if is_prime(a[j]):
cnt += 1
if cnt % 3 == 0:
ans = max(ans, sum)
print(ans)
Решение 2 (эффективное)
def is_prime(n): # функция для проверки числа на простоту
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
f = open(’Задание_27B__1v50x.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности
s = 0 # сумма всех чисел файла
count = 0 # количество простых чисел всего файла
K = 3 # чему должно быть кратно количество простых чисел
tails = [10**30]*K # список, в котором под каждым индексом будут записаны минимальные префиксные суммы.
# определенный индекс обозначает остаток при делении на 3.
# Например, tails[2] - это префиксная сумма, у которой количество просто чисел даёт остаток 2 при делении на 3
for i in range(n):
x = int(f.readline()) # считываем текущее число
s += x
if is_prime(x): # если текущее число - простое
count += 1 # увеличиваем счётчик
if count % K == 0: # если счётчик кратен 3
mx = max(mx,s) # перезаписываем максимум
# если в сумме s количество простых чисел не кратно 3
# тогда убавляем такую префиксную сумму,
# после которой в полученной подпоследовательности количество простых чисел будет кратно 3
s1 = s - tails[count % K]
mx = max(mx,s1) # перезаписываем максимум
# перезаписываем префиксные суммы под определенным остатком при делении на 3
tails[count % K] = min(tails[count % K], s)
print(mx)