Разложение на простые слагаемые
Любое целое число большее 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
Пример
Пример входных данных11 |
Пример выходных данных6 |
| ← Превращение | Список задач | Анаграммы → |