Розклад на прості доданки

Довільне ціле число більше 1 можна єдиним способом представити у вигляді добутку простих множників (якщо перераховувати множники у неспадаючому порядку). Але якщо спробувати представляти цілі числа у вигляді суми простих доданків (також у неспадаючому порядку), то таких розкладів виявиться декілька. Наприклад, для числа 11 є 6 таких ракладів: 11=11, 11=2+2+7, 11=3+3+5, 11=2+2+2+5, 11=2+3+3+3, 11=2+2+2+2+3.

Напишіть програму, яка шукає кількість розкладів заданого числа на прості доданки.

Технічні умови

Вхідні дані

Натуральне n (1 < n ≤ 5000).

Вихідні дані

Кількість розкладів заданого числа на прості доданки.

Інформація про задачу

Ліміт часу: 3 секунди
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 12.5
Складність: 65% 11/31

Приклад

Приклад вхідних даних

Приклад вихідних даних

← Пертворенння

Список задач