2. Разложение на простые слагаемые

Самая сложная задача. 15 баллов можно было получить с помощью рекурсивного перебора. Полное решение требует одновременно применения "длинной" арифметики (только сложение), динамического программирования и алгоритма для проверки числа на простоту. Самый сложный элемент – динамическое программирование. Количество разложений данного числа `N` на простые слагаемые является суммой по всем простым числам `P\ ≤\ N` количеств разложений числа `(N–P)` на простые слагаемые меньшие или равные `P`. Для `N\ =\ 0` существует 1 (пустое) разложение. При правильной организации вычислений необходим только один массив, в котором постепенно будет накапливаться количество разложений числа `I` на простые слагаемые меньшие и равные `P`.