How to find a subset of numbers from 2 to 1000 that will give you the max sum under the condition that any two numbers from the subset don't share common prime factors (e.g., 1000 and 500 share the prime factor 2)?
One (maybe easier) variation to the above question: what is the largest number in the subset? We know that 997 is a prime number, and it is easy to rule out 1000 and 998, thus the question becomes whether is 999 in the subset?
Create a graph with nodes {2, ..., 1000}, and edges when nodes have gcd > 1. Solution to this problem is same as finding maximum-weight independent set problem, which is NP-hard except in some special cases. This graph case doesn't look like a spacial case from list on Wikipedia page or even on this list.
Update
As James suggested it is possible to reduce number of nodes in this graph. Lets say that signature of a number N with prime decomposition p1^k1*...*pn^kn is a tuple (p1, ..., pn).
First reduction is to remove nodes when there is nodes with larger value and same signature. That reduces graph to 607 nodes.
Next reduction is to remove node N with signature (p1, ..., pn) if there are nodes with signatures that is decomposition of (p1, ..., pn) and there sum is >= N. That reduces graph to 277 nodes.
From these nodes 73 are isolated nodes (primes > 500.)