Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
There are 10 primes before number 30.
Label primes from {2, 3, … 29} with {0,1, … 9} and let DP(i, mask) denote the number of subsets before index: i with the subset of taken primes: mask.
If the mask and prime factorization of nums[i] have a common prime, then it is impossible to add to the current subset, otherwise, it is possible.