in reply to Matrix Formation
So, your problem is reduced to factoring each of the N^N integers and somehow intersecting the resulting sets of factors.
Quantum::Superpositions claims to make factoring trivial (and possibly the rest of the program, as well).
Update: Hey, Look! Here's a new Q&A node that finds the intersection of sets. I wonder if it handles repeated items, since factorings may look like 8 = (2, 2, 2) or 45 = (3,3,5) for examples...
You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.