minimize sum of primes with a lower bound on product
I'll suggest a very simple and very fast algorithm that I believe produces the correct result unless n is very large. 

Step 1: If n = 1 the solution is {}. If n = 2 or n = 3 the solution is { n }. Otherwise, find the smallest prime p such that the product of the primes from 2 to p is ≥ n. Let S = the set of primes from 2 to p, let P = the product of the primes from 2 to p. If p &lt; 2n then the result is S. 

Otherwise, let r be the largest prime such that P / r ≥ n. Also, let q be the smallest prime > p, and let r' be the largest prime such that (P * q / p) / r' ≥ n. If r' - r > q - p then the result is S + { q } - { r', p }, otherwise the result is S - { r }. 

The first n where this doesn't give the optimal solution is n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1 ≈ $2.622·10^{36}$.

Reasoning: We would want to use the smallest primes possible, because the ratio P / log p grows as p grows (with the exception of the primes 2 and 3). The exception is when we have a product that is quite a bit larger than n, and may get a product closer to n with a smaller sum. 

If P &lt; 2n, then we might replace p with a larger prime q and remove the prime 2 from the product. But q ≥ p + 2, so the sum of primes will not get smaller. 

If P ≥ 2n, then removing the largest possible prime from the product will obviously make the product smaller. This does not give the optimal solution if for example P / 7 ≥ n but P / 11 &lt; n, the next prime after p is q = p + 2, and replacing p with q in the product means that (P * q / p) / 11 ≥ n. In this case we increased the sum by 2 replacing q with p, and decreased it by 4 replace r with r'. But the algorithm will find this case. 

This does not detect the case where replacing p with the next prime after q would improve the sum. Let q be the smallest prime > p, and q' the smallest prime > q. We know that q' ≥ p + 6 because p, p+2 and p+4 cannot all three be prime. So we might not find the optimal solution if the prime after r is r+8. 

This is the case for the first time when r = 89 and the next prime is 97 = p + 8. If p = 101, then q = 103 and q' = 107 = p + 6. So take n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1: We need all the primes up to p = 101 to have a product P ≥ n. We can leave out r = 89 from that product, but not 97 because the remaining product is much smaller than n. If we exchange 103 for 101, we still cannot remove 97 because the product would be n-1. But we can exchange 107 for 101 and remove 97 instead of 89 from the product, getting a sum that is smaller by 2. So the optimal solution here is { 2, 3, ..., 83, 89, 107 } where the algorithm will return { 2, 3, ..., 83, 97, 101 }.