As Patrick87 points out, $\forall m,n\ge 2 : mn \ge m+n$, so we always want to construct using prime factors.
Denote the target block sizes as $\{t_i\}$. We can express the construction costs as a directed graph with vertices corresponding to $\mathbb{Z}^+$ and edges $n\to pn$ with weight $p$ for all $n$ and all prime $p$. The task is to find the connected subgraph containing $\{t_i\} \cup \{1\}$ which has least total weight.
We can make the following observations:
If there is only one target, $n$, the optimal solution is $\text{sopfr}(n)$ where sopfr (A001414) is the sum of prime factors with repetition. In fact we can claim a stronger property: any path from $1$ to $n$ will have total weight $\text{sopfr}(n)$, differing only in the order of the primes.
If the targets can be partitioned into $\{a_j\}, \{b_k\}$ such that $\forall j,k : \gcd(a_j, b_k) = 1$ then the problem can be split into independent subproblems for the $\{a_j\}$ and $\{b_k\}$. Proof: if a vertex other than $1$ is included in the optimal subgraph for the $\{a_j\}$ then it is not a factor of any of the $\{b_k\}$, and hence were it in the optimal subgraph for the $\{b_k\}$ it could be removed, contradicting the optimality.
If there is a common divisor $d$ of all the $\{t_i\}$ then we can reduce to the problem with targets $\left\{\frac{t_i}{d}\right\}$ and add $\text{sopfr}(d)$ to get an optimal solution. As Ross Millikan observes, this is obvious; it's easy to prove when there are only two targets, and when there are more I believe a proof by contradiction is possible, although not very elegant.
This is already a complete solution for $|\{t_i\}| \le 2$.
In the non-trivial case with three targets they must be decomposable as $axy, bxz, cyz$ where $x,y,z>1$ and $\gcd(ay,bz) = \gcd(ax,cz) = \gcd(bx, cy) = 1$. Then suppose wlog that we construct the first pairwise GCD, $x$. This leads to total cost $\begin{eqnarray}C & = & \text{sopfr}(x) + \text{sopfr}(ay) + \text{sopfr}(bz) + \text{sopfr}(cyz) \\ & = & \text{sopfr}(x) + 2\text{sopfr}(y) + 2\text{sopfr}(z) + \text{sopfr}(a) + \text{sopfr}(b) + \text{sopfr}(c) \end{eqnarray}$ Therefore it is optimal to construct the pairwise GCD with the greatest sopfr in this case. (NB not necessarily the greatest pairwise GCD - consider $\text{sopfr}(8) = 6 < \text{sopfr}(7)$).
If you just need a better-than-trivial approximation the following greedy strategy is better than nothing:
- Apply the three observations above, if applicable.
- Otherwise find the pair of targets $t_j$ and $t_k$ with the pairwise GCD with greatest sopfr, $d$; solve for targets $\{t_i | i\ne j \wedge i\ne k\} \cup \{d\}$; and add $\text{sopfr}\left(\frac{t_j}{d}\right) + \text{sopfr}\left(\frac{t_k}{d}\right)$.
But there's a reduction from vertex cover which proves that the problem is NP-complete, so don't hold out much hope for a tractable general solution.
With credit to user946850 for the key idea:
We sketch an argument that the problem is NP-complete by reduction from the vertex cover problem. Since NP is formally a class of decision problems, we must restate the problem in a decision form:
Given target block sizes $\{t_i\}$ and a target cost $T$, is it possible to construct all of the target sizes with total cost not exceeding $T$?
The vertex cover problem is stated as:
Given a non-directed graph $G = (V, E)$ and a target cover size $k$ does there exist a subset $S \subseteq V$ such that $|S| \le k$ and $\forall (v_i, v_j)\in E : v_i \in C \vee v_j \in C$?
We can assume wlog that the graph is connected, so (abusing notation by allowing the sets in a scalar context to be interpreted as their sizes) $E = \Omega(V)$ and $E = O(V^2)$.
The reduction strategy we take is to map each $v_i \in V$ to a distinct prime $p_i$ and each edge $(v_i, v_j) \in E$ to a target block size $p_i p_j$. Then any vertex cover $C'$ can be represented as building the primes corresponding to the vertices in $C'$ and from these building the targets. The cost will be the sum of $|C'| + |E|$ non-distinct primes drawn from $\{p_i\}$. If we call the smallest of the primes used $p_{min}$ and the greatest $p_{max}$, we can set a target cost of $(k + E)p_{max}$ and it is sufficient that $(k+E+1)p_{min}$ is greater for the answer given by the reduced problem to be the answer to the original problem.
Therefore we need to find a prime $p_{min}$ such that there are $V$ primes in the half-open interval $[\;p_{min},\;(1+\epsilon)p_{min})$ where $\epsilon^{-1} = k + E$. We also need to identify all $V$ primes. Here we will keep things simple (hence "sketch an argument" rather than "prove") by merely using the simplest form of the prime number theorem. We're going to check $\Theta(\epsilon\; p_{min})$ numbers for primality, and we need $V$ hits, so we want $\frac{p_{min}}{\log p_{min}} = \Theta(\epsilon^{-1} V )$. This will give $p_{min} = O(E^2 V^2)$ (which can be strengthened to $p_{min} = O((EV)^{1+\alpha})$ for any $\alpha > 0$), which is polynomial in the size of the input to the vertex cover problem, that input size being $\Theta(E \log V)$. The number of candidate numbers which must be checked is also polynomially bounded, and since their sizes are polynomially bounded and primality testing is in P the total cost of performing the reduction is polynomial.