Subtask 1

The key observation to this problem is that after sorting, it is optimal to greedily fill groups. Specifically, take the smallest element, create a group containing all multiples of this element, and repeat. Proof is left as an exercise.

For this subtask, we can do this naively.

Time Complexity: ~\mathcal O(N^2)~

Subtask 2

For the full solution, we can do a Sieve of Eratosthenes-like approach, marking all multiples as found. Specifically, use a boolean array, each time an element is not already marked, mark all its multiples and increment the counter.

Time Complexity: ~\mathcal O(\max(J_i)\ \log N)~