I have an almost impossible to remove malware/virus. Need help.

[AC Question]

I bought a galaxy s5 like 6 months ago, and from the beginning I have had an annoying as **** malware/virus, which every time that I open a link, whether it's from an app, or browsing through Google Chrome, I get **** like this (those are screenshots of what the malware/virus shows me) [apparently I cant post links]

And it doesn't let me go back, I need to close all the apps, and go back, but hey that stupid **** appears again. Tired of this ****, I went to a store that repairs phones and that, and the guy said the only way was to make a factory reset, he did it once, and yet I still had the exact same issue, and then a second time, and I STILL HAVE THE FREAKING ISSUE. I have NO APPS installed right now, not even my SD card on, I have nothing, it's totally clean the phone, and yet I still get this crap.
Sorry for the bad words, but this phone is a pain in the ***, I had an iPhone for 3 years, and never had this kind of issues. If someone could please please please tell me what this crap is and how can I solve it, I would appreciate it.

 

[belodion]

You may need to reflash the OS.

Incidentally, I've experienced this sort of thing, though not OS-deep, on my iPhones, and only on them.