Selecting a good collection of primers is very important for polymerase chain reaction (PCR) experiments. Most existing algorithms for primer selection are concerned with computing a primer pair for each DNA sequence. We consider selecting a small set of primers which amplify all DNA sequences by allowing each primer matches several places. This is quite useful because deceasing the number of primers greatly reduces the cost of biological experiments. First, we formulate the primer selection problem and analyze the complexity of these problems. A simple formulation to cover all sequences can be reduced to a set cover problem. By using the greedy algorithm, we obtain a nice collection of primers in this case. Due to the necessity of resolving amplified parts by electrophoresis, the length of each amplified part by PCR should be different. With this length constraint, the problem is shown to be much harder to solve from the complexity and approximability viewpoints. Our results demonstrate that a clear complexity gap exists between cases with and without the length constraint. Next, we implement the greedy algorithm for the simple formulation and apply it to real yeast data. It is observed that solutions by this greedy algorithm do not satisfy biological constraints, such as minimum length constraint and distinct length constraint for amplified segments. We extend the greedy algorithm by introducing prohibitive conditions to satisfy the biological constraints, by which a good solution is obtained. Finally, we construct algorithms which design the sets of primers for multiple experiments by extending these greedy algorithms. We obtain primer sets which distinguish half of all yeast DNA sequences.