Python задача . .

Question

Python задача . .

Soul Leveling Ученик (70), на голосовании 2 дня назад

Задача:
Дан массив чисел длины n.
Необходимо ответить на q запросов.
Каждый запрос содержит числа l и r.
Требуется вычислить сумму чисел на отрезке от l до r после следующего преобразования:
Если число на позиции i является простым, заменить его на его квадрат, иначе оставить без изменений.
Ограничения:
1 <= n <= 10^5
1 <= nums[i] <= 10^9
1 <= q <= 10^5
1 <= l <= r <= n

 Тестовые данные:  
  Ввод:  
  5 3  
  2 4 5 6 7  
  1 3  
  2 5  
  1 5  
  Вывод:  
  29  
  77  
 106

Answer 1

Тестовое задание НЕ соответствует условию задачи.
Исходный массив: 2 4 5 6 7
Меняем простые числа на их квадраты: 4 4 25 6 49
1 3: 4 + 4 + 25 = 33 ≠ 29
2 5: 4 + 25 + 6 + 49 = 84 ≠ 77
1 5: 4 + 4 + 25 + 6 + 49 = 88 ≠ 106

Но если хочешь код, решающий задачу так, как ты её сформулировал, то:

 import math

def is_prime(x): # проверка числа на простоту
  if x < 2: return False
  if x % 2 == 0: return x == 2
  for i in range(3, math.isqrt(x) + 1, 2):
    if x % i == 0: return False
  return True

_, q = map(int, input().split()) # число n не требуется

t = [0] + list(map(int, input().split()))
for i in range(1, len(t)): t[i] = t[i - 1] + t[i] * [1, t[i]][is_prime(t[i])]

for _ in range(q):
  l, r = map(int, input().split())
  print(t[r] - t[l - 1])

t[i] равно сумме уже преобразованных входных чисел с индексами от 1 до i включительно. Плюс добавлен равный 0 элемент с индексом 0.