An accelerated Monte Carlo code [Monte Carlo dose calculation for prostate implant (MCPI)] is developed for dose calculation in prostate brachytherapy. MCPI physically simulates a set of radioactive seeds with arbitrary positions and orientations, merged in a three-dimensional (3D) heterogeneous phantom representing the prostate and surrounding tissue. MCPI uses a phase space data source-model to account for seed self-absorption and seed anisotropy. A "hybrid geometry" model (full 3D seed geometry merged in 3D mesh of voxels) is used for rigorous treatment of the interseed attenuation and tissue heterogeneity effects. MCPI is benchmarked against the MCNP5 code for idealized and real implants, for 103Pd and 125I seeds. MCPI calculates the dose distribution (2-mm voxel mesh) of a 103Pd implant (83 seeds) with 2% average statistical uncertainty in 59 s using a single Pentium 4 PC (2.4 GHz). MCPI is more than 103 and 104 times faster than MCNP5 for prostate dose calculations using 2- and 1-mm voxels, respectively. To illustrate its usefulness, MCPI is used to quantify the dosimetric effects of interseed attenuation, tissue composition, and tissue calcifications. Ignoring the interseed attenuation effect or slightly varying the prostate tissue composition may lead to 6% decreases of D100, the dose delivered to 100% of the prostate. The presence of calcifications, covering 1%-5% of the prostate volume, decreases D80, D90, and D100 by up to 32%, 37%, and 58%, respectively. In conclusion, sub-minute dose calculations, taking into account all dosimetric effects, are now possible for more accurate dose planning and dose assessment in prostate brachytherapy.