HP laptop shutting down

Hi! I have an HP Laptop and for the past week or so, it has been shutting down. If I'm on the online game I like to play with my friend, it shuts down after about 2-3 minutes. If I'm just on the internet, it will shut down after about an hour, depending on what website I'm on. When I turn it back on, it displays the overheating message that is on Windows. I know that it isn't overheating (or is it?) because at one point I left it turned off for a day and a half and it shut off a few minutes after I turned it on. My father thinks it might be an issue with the fan.

I usually have the laptop on a table in my room when I'm using it, so I'm not blocking any air vents. Will someone please tell me what's happening to my laptop, and or tell me how to fix it? I would gladly appreciate all the information I can get.

I've also used all 6 (I think) computer cleaning programs that come with windows (maybe a few more that I installed) and even though I've cleaned it in every way possible, it's still not working. Thanks for the help.

~Edit

Oh yes, and when it turns off, I have to wait about 5-10 minutes before trying to turn it back on, otherwise it will just shut down again in the middle of turning on. Just thought it might be useful to know, because I'm sure you guys out there fixing computers need all the information you can get.

And if it can't be fixed, then does anyone have any advice on a laptop that would be able to handle lots of gaming? Because I'm kind of leaning toward putting all of my documents on a flashdrive, buying a gaming laptop, and putting my stuff on their to get rid of this one that I was talking about. I do a lot of gaming, so I'm guessing that might be why my laptop isn't working.
 
The fan draws in dust over time and it gets lodged into the cooling fins for the CPU and video processor. This causes the motherboard heat sensor to shut down the laptop. A person with laptop repair experience can fix this easily, but the thermal paste on the CPU and the thermal pads may also need to be replaced
 
Thanks! I'll have to have someone look at that! Thanks so much for the help. I'll remember to come back here when my laptop isn't working in the future! :)
 
Back