Problem : I give you a number n >= 2. Now you generate all the prime numbers <= n (say p1, p2, p3... pn). Now I ask you to divide the prime numbers into the minimal number of groups such that product of all the prime numbers within the group <= n. Give an algorithm for the same.

Solution : One possible solution for the same which I read somewhere is that work greedily. Namely pair 2 with the largest possible prime say pj such that 2*pj <= n. Then work with the next prime number (3 in most cases). Until you exhaust all the primes. This will be a minimal number of groups.

I am not able to think of the proof for the same. Any intuition or alternate solution would be highly appreciated.

Here is the link to the problem:

http://www.spoj.pl/problems/EXPRESS/

And here is the link to my solution:

http://ideone.com/Oq9RI

The solution gets a Time Limit Exceeded on SPOJ. I have first transformed the Postfix expression to a Infix tree and then I simply used a queue to reverse the described process(in the problem). Is this solution so slow or is this due to the input/output that I am facing TLE?

Here is the link to the the SPOJ problem FREQUENT: https://www.spoj.pl/problems/FREQUENT/ And here is a link to my solution http://ideone.com/7XiVC I used segment trees to solve the problem keeping the left end number/frequency, the right end number/frequency and the maxfreq number/frequency of a segment. But I am receiving a WA. Could anyone tell me the problem.