Hi. I am trying to solve this problem.

For convenience, I have replicated the problem statement below:

Given a list of N integers (non-distinct) where and each integer , sort the integers based on the lexographical order of their prime factorization.

Example (the first number is N):

5
2 3 4 5 6

Expected Output:

2
4
6
3
5

Explanation:

2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3

Time limit is 2s and memory limit is 32mb.

My attempt:

I used a fast factorization method to factor each integer into its prime factors and store them into a 2D matrix, M. M[i][j] represents the j^th prime factor of the i^th integer in the list such that M[i][j] ≤ M[i][j + 1].

Now, I use a custom sort method to sort the list. Let's say we want to compare integers at position u and v in the list.The sort function will compare M[u] and M[v] using lexicographical comparison.

My code.

This method is correct but it will get MLE (not TLE surprisingly). I tried asking this problem on stackoverflow but could not obtain a satisfactory answer. Could someone please advise me on a better way to solve this problem?

p.s. not sure if this info would be helpful — this problem is tagged with dfs in the source.