Sort a list of integers by prime factorization

Revision en3, by Lance_HAOH, 2017-11-22 05:42:57

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 lexicographical 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 jth prime factor of the ith 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.

Tags #sorting, #primes, #dfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Lance_HAOH 2017-11-22 05:42:57 2 Tiny change: 'on the lexographical' -> 'on the lexicographical'
en2 English Lance_HAOH 2017-11-22 05:18:33 8
en1 English Lance_HAOH 2017-11-22 05:09:13 1482 Initial revision (published)