I see repeated annoying pop-up messages claiming I have viruses. When I click "Remove Virus", I'm sent to the Google Play store. What should I do? this pops up whenever I lock my phone and unlock it. How do i fix this?

 

I'm using a Samsung Galaxy Note 3. When i click on 'remove virus now' it redirects me to a page on google play store which shows a cleaner app.
Visit a different site (and avoid this one in the future). That's a fake warning wanting to trick you into some download. Definitely do NOT hit that button labeled "Remove virus now" – if you do that, you'll have your device infected with some malware for sure. Don't get irritated by the Google logo, this is not a message from Google (they have other ways for "desinfection").

Never trust any such popup if it says your Android device has viruses – there are no viruses on Android (malware yes, but no viruses – there's a subtle difference). Second proof: a website cannot scan your device for malware, so how will it know?

One more pointer is the "countdown" in the second screenshot, which clearly identifies the message as Scareware: No sincere and trustworthy software would issue an ultimatum to the user. The only intention here is forcing you to "switch off your brains in panic".

So either that website got infected – or it's even an intentional malicious site. Your device is fine.