If Windows 8.1 was on your laptop when you bought it, you must use your laptop's dedicated recovery media to reinstall Windows or ask the laptop vendor for help with the product key.
However, I suspect we are not talking about an OEM copy. In your title, you've said "Windows 8" while in your message body, you exclusively said "Windows 8.1". These two require different product keys. If you've upgraded your Windows 8 via Windows Store, you should do it again, i.e. install Windows 8 and upgrade it via Store or Automatic Update (recently available). I've heard rumors that it is possible to install a Windows 8.1 without supplying a product key (hence, in trial mode) and after installation, use DISM to set the product key to Windows 8's. The rumor goes that doing so allows you to activate Windows 8.1 successfully. The Wikipedia article on Windows 8.1 has a lot of leads on this. (Actually, it is a descent article too.)
Whatever happens, if and when you resolved the issue, consider creating a recovery image; a full image of the installed Windows. From that point forward, instead of a clean install, you do a clean recovery. Windows itself provides abundance of help in this matter.