Finding longest coprime numbers subsequence in polynomial time

[choxy]

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!

 

[joel76]

It's not Prolog, it's algorithmic.

 

[choxy]

I have mistake in my example: correct X = [1,5,8,9,4].

Yes, problem is algorithmic, but I need solution in Prolog, so I hoped that someone is familiar with both of them (algorithm and Prolog) and can guide me.

Maybe someone knows, where could I found algorithmic guides for this problem?