I have to find the longest list's subsequence, in which each two following numbers are coprime.
Example:l_coprime_subseq([1,5,6,8,9,18,4],X). X=[1,5,9,4]
I have to make it work in polynomial time. I can only make it work in exponential time by finding all coprime subsequences and then finding the longest list from all subsequences.
Have any thoughts how to do this in polynomial time?
Thanks!
Example:l_coprime_subseq([1,5,6,8,9,18,4],X). X=[1,5,9,4]
I have to make it work in polynomial time. I can only make it work in exponential time by finding all coprime subsequences and then finding the longest list from all subsequences.
Have any thoughts how to do this in polynomial time?
Thanks!