Problem: http://www.spoj.com/problems/ADAMOLD/ I unable to think of approach better than O(k*n^2)

Problem :ADADIG I am trying to solve this , my Approach is: For a given N : 1)If it is prime —> if single digit return 1 else return 0

2)else factorize N and find all combinations of its factor and add 1s to make the digital sum equal to be N and find all permutations of it and add them all and return this. for step 2 , I am unable to figure out How do I do that efficiently?