Prime95 is designed to synthetically stress out your CPU to it's maximum. You might get temps considerably higher with Prime95 than you would during a non-synthetic (real world) load.
Also, air has a significantly less specific heat capacity than liquid, so it will heat up to it's maximum temperature and cool down to it's idle temperature almost immediately, whereas with liquid cooling, temps will appear very low at first and gradually increase to their maximum over time. So understand this coming from a liquid cooling background.
Beyond this, you can make sure the thermal compound is applied adequately over the IHS (the observable processor) to ensure maximum contact. If the thermal compound isn't covering the die (where the cores are, generally in the middle of the processor) you might be getting higher temps. This can also happen if there are air bubbles in the paste as well, even if they're microscopic. This is worsened if you slide the heatsink across the thermal paste during installation. It can make a big difference. Make sure it's not too tight, but also that it's not falling off. You don't want it to be 100% rigid, but you don't want it to slide around like crazy.
Once with one of my fin heat-sinks, the metal stand on the bottom was bent and it wasn't making flush [flat] contact with the IHS because of this. It wobbled a bit, but properly installed, only wiggled a bit flat across the IHS.
I recommend re-installing and re-applying thermal paste. The pea or dot method is fine, but don't add "too much" or "too little", as this can impact cooling significantly, too. If you're using the stock paste and don't have any left, Arctic MX-4 is good, and Thermal Grizzly "Kryonaut" (Kryonaut specifically) is probably the best safe option for thermal paste, but the Kryonaut is much more expensive, and the difference might only be a handful of degrees C.
MX-4 is 8.5 W/mK and Kryonaut is 12.5 W/mK, but the price is ~$6 to ~$20 for about 4 grams.
After this, if you're overclocking, 80C peaks in Prime95 should be okay, but at stock, it shouldn't be that high, but Prime95 IS known for making things seem hotter than they otherwise should be.
Reapplying and reseating should help a lot. Making sure you have enough air intake and exhaust fans will help a lot, too, if that isn't already obvious.
Ambient temperature (the temperature of your room) can also play a big role on CPU temperatures. If it's already 35C in your room, an idle temperature of 35C is a little more reasonable.