PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:Easymedium PREREQUISITES:Dynamic programming, prime factorization PROBLEM:Given a list of positive integers, find the size of the largest pairwisecoprime sublist. QUICK EXPLANATION:Let's call a prime number small if $p \le \sqrt{1000}$, i.e., $p \le 31$. There are $11$ such primes, so a set of small primes can be represented by a bit set of $11$ bits. Let $S(k)$ be the set of small prime factors of $k$. Sort the list $a_1, \ldots, a_n$ by their largest prime factor. Then, if $S$ is a set of small primes, define the function $F(i,S)$ as the size of largest pairwisecoprime sublist of $a_1, \ldots, a_i$ such that are also pairwisecoprime with $S$. Then the answer we're looking for must be $F(n,\emptyset)$. $F(i,S)$ can be computed with the following recurrence: For the base case, we have $F(0,S) = 0$ for any $S$. EXPLANATION:Two numbers are coprime if and only if they don't share a common factor. This allows us to check whether two numbers are coprime without having to compute $\gcd$. Let $P(k)$ be the set of prime factors of $k$. For example, $P(980) = \{2, 5, 7\}$. Then $a$ and $b$ are coprime if and only if $P(a) \cap P(b) = \emptyset$. This formulation also gives us a straightforward dynamic programming solution. Suppose the numbers are $[a_1, a_2, \ldots, a_n]$. If $S$ is a set of primes, let $F(i,S)$ be size of the largest pairwisecoprime of $[a_1, a_2, \ldots, a_i]$, assuming the primes in $S$ have already been taken, i.e., no prime in $S$ appears as a prime factor in the sublist. Then the answer that we want is $F(n,\emptyset)$. $F(i,S)$ itself can be computed with the following recurrence: To understand the recurrence, notice that there are two types of pairwisecoprime sublists of $[a_1, a_2, \ldots, a_i]$.
So, $F(i,S)$ must be the larger between these two. Unfortunately, this runs very slowly. To see this, note that there are $168$ primes below $1000$, to the number of possible sets $S$ is $2^{168}$, which is a very large number! Small and big primesWe can improve this solution by noticing that every prime $> \sqrt{1000}$ only ever appears alongside primes $\le \sqrt{1000}$ in any number. In other words, suppose we call a prime number small if it is $\le \sqrt{1000}$ and big otherwise. Then a number cannot have two big prime factors at the same time, because suppose $n$ has the big prime factors $p$ and $q$. Then $n \ge pq > \sqrt{1000}\sqrt{1000} = 1000$, which violates the constraints. This means that we can handle big primes specially. For example, consider a big prime factor $p$. Consider the list of values that are multiples of $p$. We can select at most one number in that list, and after choosing that number, we can basically ignore the prime factor $p$! In other words, we don't have to add $p$ to the set $S$ because the remaining numbers don't have $p$ as a prime factor. This gives us an improved version of our DP solution. First, we sort the list $[a_1, \ldots, a_n]$ in increasing order of their largest prime factor. This way, for each big prime $p$, its multiples will appear consecutively in the array. Next, we define $S(k)$ as the set of small prime factors of $k$. Next, we redefine $F$ so that $S$ only contains the set of taken small primes. Now, the answer is still $F(n,\emptyset)$, but the recurrence for $F(i,S)$ becomes slightly different. Consider a particular $F(i,S)$. Again, there are two types of pairwisecoprime sublists:
As before, $F(i,S)$ must be the larger among these two candidates. More formally, we now find the following recurrence for $F(i,S)$:
Now, this time, there are only $11$ small primes, the number of possible sets $S$ is now just $2^{11} = 1024$, and the number of distinct valid arguments to $F$ is $(n+1)\cdot 2^{11} = 2050048$, which is much more manageable. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Jun '16, 15:17

This is a reply for above greedy answer check this test case
output should be 2 becoz we can select 42 and 715 which are coprime. But your approach will give o/p 1. first nos will be sorted according to the no of prime dvisors. 10(2,5),42(2,3,7),715(5,11,13) have 2,3,3 prime divisors respectively. So, after sorting u will get 10,42,715 once u will mark prime divisors of 10(2 & 5), u will not be able to include 42 and 715 in answer as they have prime div which is already used(2&5). So,greedy soln will give o/p 1, which is wrong. answered 03 Jun '17, 13:29

i am trying to solve this question greedily. i sort the list of input numbers according to the number of different prime divisiors in ascending order. then there is the list of used prime numbers. then i traverse each of the input numbers in above mentioned order and for each number, if all the prime divisors are not used, mark them used in the prime number list and add 1 to ans. getting WA. pls help. SAMPLE 5 1 2 3 4 5 DIFFERENT PRIME DIVISORS (sorted list) 10 20 30 50 41 traverse above list if(1) add 1; else check all prime divisors of number (for 2,check 2, if !used,mark and add 1 to ans) for 4 it checks 2 which is used so nothing is added pls help where this approach fails answered 19 Jul '16, 09:15

"Two numbers are coprime if and only if they share a common factor", something wrong with this statement in the first line of explanation!
@lohit_97 Corrected. Thank you!