set with maximum sum consisting of mutually co-prime numbers
Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating. 

Since the numbers are mutually co-prime, each prime number p is a factor of at most one element of S. On the other hand, if p is small enough then a number could have a factor $p^2$, $p^3$, $p^4$ and so on. We also know that every prime number p ≤ N is used (if p is not used as a factor of any number in the set then we just add p). And don't forget to include the number 1 in the set S :-)

A number x ≤ N cannot have two prime factors greater than $N^{1/2}$. Therefore the set S contains among other numbers one number $x_p$ ≤ N which is a multiple of a prime $p &gt; N^{1/2}$. That's a good start for finding the optimal set S. We then take the primes $q ≤ N^{1/2}$, and either multiply one of the numbers $x_p$ by a power of q, or we add a new number $x_q$ which is some power of q. 

In the Project Euler project with N = 200,000, there are fewer than 90 primes $q ≤ N^{1/2}$. We can take each of these primes q in turn, and either multiply one of the existing $x_p$ by a power of q, or add a new number $x_q$. We would try to do this achieving the highest possible increase in the sum. If no two q, q' achieve the highest increase in the same way, we can pick the optimal way for each. 

In the example N = 30, we would start with $x_p$ = 7, 11, 13, 17, 19, 23, 29. We can use q = 2 to change 7 -> 28. q = 3 -> 27, q = 5 -> 25. The gains are 21, 27, 25. Each gain is > N/2. So an optimal solution cannot include a number created by two or more of the q's - that number would be ≤ N, but we would give up two gains > N/2, so this wouldn't be optimal. So in the simple example, we multiply 7 by $2^2$ and add $3^3$ and $5^2$. 

With N = 100, we would have $x_p$ = 11, 13, 17, 19, 23, ... and q = 2, 3, 5, 7. q = 2: 11 -> 88 gains 77. q = 3: 11 -> 99 gains 88. q = 5: 19 -> 95 gains 76. q = 7: 13 -> 91 gains 78. Unfortunately we have a conflict; q = 2 and q = 3 would both use $x_{11}$. If we use 11->88 (gain 77), then q = 3: 31->93 with a gain of 62; total gain 139. If we use 11->99 (gain 88) then q = 2: 23->92 (gain 69) has a total gain of 157. So optimal for N = 100 is

S = { 1, 99, 91, 17, 95, 92, 29, 31, 37, 41, ,,, }


So here is the algorithm: Start with $x_p$ = primes > $N^{1/2}$. Find the primes $q ≤ N^{1/2}$. For each q, find the maximum gain that can be achieved using q: Either $q^k$ by adding the number $q^k$, or $p * (q^k - 1)$ by multiplying $x_p$ by $q^k$. If each optimal gain is achieved in a different way, and each gain is ≥ N/2, then we found the optimal solution. 

Otherwise, we choose one set of q's that use the same $x_p$. For each of these q's: We assume that this q uses $x_p$, find the optimal solution under the restriction that no other q uses this $x_p$, and choose which q using $x_p$ gives the best total. 

If there is a case where the two smallest gains add up to less than N, ask someone for a more complex solution :-)