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.