Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Finding longest coprime numbers subsequence in polynomial time

Status
Not open for further replies.

choxy

Programmer
Apr 15, 2009
2
0
0
LV
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!
 
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?
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top