Replica exchange molecular dynamics (REMD) simulations have become an important tool to study proteins and other biological molecules in silico. However, such investigations require considerable, and often prohibitive, numerical effort when the molecules are simulated in explicit solvents. In this communication we show that in this case the cost can be minimized by choosing the number of replicas as N-(opt) approximate to 1 + 0.594 root C ln(T-max/T-min), where C is the specific heat, and the tempertures distributed according to T-(opt) approximate to T-min(T-max/T-min)((i-1)/(N-1)).