We classify all the K3 surfaces which are minimal models of the quotient of the product of two curves C1 x C2 by the diagonal action of either the group Z/pZ or the group Z/2pZ where p is an odd prime. These K3 surfaces admit a non-symplectic automorphism of order p induced by an automorphism of one of the curves C1 or C2. We prove that most of the K3 surfaces admitting a non-symplectic automorphism of order p (and in fact a maximal irreducible component of the moduli space of K3 surfaces with a non-symplectic automorphism of order p) are obtained in this way. In addition, we show that one can obtain the same set of K3 surfaces under more restrictive assumptions namely one of the two curves, say C2, is isomorphic to a rigid hyperelliptic cu...