Задача 552
Китайские остатки II

Пусть An будет наименьшим положительным целым числом, удовлетворяющим условию An mod pi = i для всех 1 ≤ in, где pi - i-тое простое число.
Например, A2 = 5, так как это - наименьшее положительное решение системы уравнений

  • A2 mod 2 = 1
  • A2 mod 3 = 2

Система уравнений для A3 добавляет еще одно ограничение. То есть, A3 является наименьшим положительным решением для системы

  • A3 mod 2 = 1
  • A3 mod 3 = 2
  • A3 mod 5 = 3

и потому A3 = 23. Таким же образом можно получить A4 = 53 и A5 = 1523.

Пусть S(n) будет суммой всех простых чисел до n включительно, которые являются делителями хотя бы одного элемента последовательности A.
Например, S(50) = 69 = 5 + 23 + 41, так как 5 является делителем A2, 23 является делителем A3 и 41 является делителем A10 = 5765999453. Ни одно другое простое число до 50 включительно не является делителем элемента последовательности A.

Найдите S(300000).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net