11353 - A Different Kind of Sorting
Solution Description : Prime factor and sorting problem 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. |
||||||||||