Samsung Galaxy S4 Active — I think my S4 has viruses.

I was on my phone when I was getting tons of pop-ups from Samsung saying

locationservices is not a trusted app

cat(something) is not a trusted app

And some other things saying the same thing.
My first reaction was to reformat my phone, and I did.

But during the setup process it said.

locationservices

And then it would disappear.

cat(something)

And then it would disappear.

I'm letting my parents deal with it but they probably don't know how to remove it. If my phone is screwed, i'm not getting a new one. Please help