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 2*s* and memory limit is 32*MB*.

**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.

I will use a typical sorting algo. something like a quicksort maybe. something like:

Beware this code is not tested and i havent written a quicksort in years. Also I am not sure about the complexity, but I believe it should be fast enough. EDIT: fix the arr[i]==1 part.

What does

`prime[prime_idx]`

contain?sorted prime factors

EDIT: I didnt realize this is lexicographical sorted. I believe just storing the prime factors of all the elements in the array and store it lexicographically?

Hmm. My original approach already attempts to sort the integers by lexicographical order of their prime numbers but it gets MLE. How does your approach avoid the MLE?

I am not fully sure why your approach use so many memory. You can see that my quicksort approach only use constant memory each call, which makes it fine. and my prime vector is small as there is at most 1000000 primes from 1 to 1e6? so how would it MLE?

EDIT: I see why your MLE now, you use N*21 arrray to store your factor, which is too high for the tight constraint given.

If I understood correctly, your approach will perform trial division on each integer in the list. There are about 78000 primes less than 1e6. So that means that we will do 78k * 1e6 operations. Am I right?

yes, indeed i blundered.

Sorry, after thinking through. Create a trie/graph. For each element, store it base on the prime factor. After that transverse the trie and get the number one by one base on the order.

The memory should be O(number of prime factor * depth), which should be small enough.

If I understood your new approach correctly, your approach requires me to perform prime factorization on all the numbers in the list and store these prime factor strings into a trie/graph.

Would the memory complexity be the same if I use a jagged 2D array?

If your comparison function works in you don't need to waste memory on storing the factors, you can factor the numbers while comparing them.

Hmm. That's interesting. How would you compare two integers by their prime factors in

O(logn)?The same way you extracted the prime factors themselves

That means I must simultaneously factor all the integers at once?

No, I meant, something like this:

Nice! Thanks so much for your advice. This looks like an interesting solution. I will try it out in a moment.

Got AC with this trick! Thanks so much for this short and simple solution!

Here's a nice solution:

First I'll denote the elements limit by

lim. Find all the prime numbers from 1 tolimusing sieve.Now, we will make a vector

keysof sizelim+ 1. every number X from 1 tolimwill have in keys[X] a value, which is its location if we sorted all numbers from 1 tolimby the lexicographical order of their prime factorization (that is, 1 will have key 1, 2 will have key 2, 4 (2 * 2) will have key 3...).To do this, we will create all the prime factorizations by lexicographical order. That is, we will first create all those that are just with 2's, then we will invlove 3 in the prime factorization, and so on. For instance, the first numbers we will go through are:

1, 2, 4, 8, 16, ...., 524288 (2^19), 786432 (2^18 * 3^1)...

The way to do this is with a very simple recursion: we will maintain the current value we're on, and the last prime factor we took. then, we go through all the primes from the last prime we took, until the end of the vector, or until (the current prime we're on) * (the current value in the recursion) is bigger than

lim.We maintain the last prime factor since we don't want things like this to happen: 12 = 2 * 3 * 2. (This is just by the definition of the prime factorization — we go by the increasing factors.)

The above can be proved to run in

O(lim), and gives us a comparison function that works in O(1) (we just compare keys).Here is a sample code:

This works in . (Note that you can also make the sorting in

O(n) using countsort, because the keys are between 1 andlim).