Возможный дубликат:
Число как простое число

У меня есть мое домашнее задание, чертовски тяжелое, где я должен получить все четкие простые разбиения данного числа. Например, число 7 имеет пять различных простых разделов (или пять различных способов представления двух основных разделов):

5 + 22 + 53 + 2 + 22 + 3 + 22 + 2 + 3

Как видите, само число исключается, если оно простое. Мне не нужно печатать все отдельные разделы, только их количество.

Так что я немного растерялся с этим. Мне совершенно не удалось создать какой-либо код, но я думаю, что должен подходить к этому с точки зрения динамического программирования. Я только прошу несколько подсказок. У кого-нибудь есть идея? Заранее спасибо.

Максимальное введенное число - 100. Кроме того, время работы программы не может превышать 1 секунду, а ограничение памяти составляет 128 МБ.