Duplicata Possível:
Um número como peças de números primos

Eu tenho essa minha lição de casa, difícil como o inferno, onde eu tenho que pegar todas as partições principais distintas de um determinado número. Por exemplo, o número 7 tem cinco partições principais diferentes (ou cinco maneiras diferentes de representar as duas partições principais que possui):

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

Como você pode ver, o número em si é excluído no caso de ser um primo. Eu não tenho que imprimir todas as partições distintas, apenas o número delas.

Então estou um pouco perdida com isso. Fui completamente incapaz de produzir qualquer código, mas acho que deveria abordar isso de um ponto de vista de programação dinâmica. Estou apenas pedindo algumas dicas. Alguém teve uma ideia? Desde já, obrigado.

O maior número inserido é 100. Além disso, o tempo de execução do programa não pode exceder 1 segundo e o limite de memória é de 128 MB.