Mathematical models can help predict the effectiveness of control measures on the spread of HIV and other sexually transmitted diseases (STDs) by reducing the uncertainty in assessing the impact of intervention strategies such as random screening and contact tracing. Even though contact tracing is one of the most effective methods used for controlling treatable STDs, it is still a controversial strategy for controlling HIV because of cost and confidentiality issues. To help estimate the effectiveness of these control measures, we formulate two models with random screening and contact tracing based on the differential infectivity (DI) model and the staged-progression (SP) model. We derive formulas for the reproductive numbers and the endemic equilibria and compare the impact that random screening and contact tracing have in slowing the epidemic in the two models. In the DI model the infected population is divided into groups according to their infectiousness, and HIV is largely spread by a small, highly infectious, group of superspreaders. In this model contact tracing is an effective approach to identifying the superspreaders and has a large effect in slowing the epidemic. In the SP model every infected individual goes through a series of infection stages and the virus is primarily spread by individuals in an initial highly infectious stage or in the late stages of the disease. In this model random screening is more effective than for the DI model, and contact tracing is less effective. Thus the effectiveness of the intervention strategy strongly depends on the underlying etiology of the disease transmission.