Several numerical algorithms for dynamic Monte Carlo simulations of surface chemistry have been proposed in the past. The variable step size method (VSSM) is commonly used for systems where the rate coefficients are constant in time, owing to its good efficiency. If rate coefficients vary in time, the first reaction method (FRM) has been shown to be more efficient. However, the cost of this algorithm to execute a reaction step depends on the considered lattice size, which can make this method inefficient for systems involving surface phenomena on different scales. Here we propose a general and efficient algorithm, the fast first reaction method (fFRM), which has the advantages of being applicable to systems with constant and time-varying rate coefficients, and of having a computational cost per reaction step that is independent of the lattice size. An additional feature of fFRM is that it is rejection-free, which means that once a reaction class is selected, a reaction of that type will be executed. A rejection-free variant of VSSM, called rVSSM, is also presented, which leads to an approximately 15% speedup compared with the VSSM algorithm for the considered example.