11353 - A Different Kind of Sorting

Difficulty : medium

Solution Description :

Prime factor and sorting problem

This problem requires each number to be sorted by the number of prime factors. 
For find the number of prime factor, at first pre-generate prime numbers up to 1500, you can find exactly 239 prime numbers and store to array primeNum[]
Use an array num_prime_fact[] for store number of prime factors. 

For count the prime factor you can use this method
set num_prime_fact[n] =1
for i=0; primeNum[i]<=sqrt(n) ; i++ (Here 2<=n<=2000000)
----if n is divisible by primeNum[i] then set num_prime_fact[n] = num_prime_fact[n/primeNum[i]] + 1; and break the loop

You can use a vector of structure, consisting of the number and the number of factors it has.
After the vector is populated, the vector is sorted according to number of factors first, and then by the number.