The goal of this paper is to explicitly detect all the arithmetic genera of arithmetically Cohen-Macaulay projective curves with a given degree $d$. It is well-known that the arithmetic genus $g$ of a curve $C$ can be easily deduced from the $h$-vector of the curve; in the case where $C$ is arithmetically Cohen-Macaulay of degree $d$, $g$ must belong to the range of integers $big{0,ldots,binom{d-1}{2}big}$. We develop an algorithmic procedure that allows one to avoid constructing most of the possible $h$-vectors of $C$. The essential tools are a combinatorial description of the finite O-sequences of multiplicity $d$, and a sort of continuity result regarding the generation of the genera. The efficiency of our method is supported by computational evidence. As a consequence, we single out the minimal possible Castelnuovo-Mumford regularity of a curve with Cohen-Macaulay postulation and given degree and genus.