Ok I'm going give you couple more things to try out before I say factory reset
1. Make sure you try both WiFi and mobile data turn off one at a time , if still issue go settings>general management>reset>reset network
2. General management>reset>reset settings
3. Settings>apps>3 dots upper right corner tap reset apps preference
Go to app info for Google play services and then scroll to the bottom where it says installed by play store. It will take you to it in the play store and see if there is an update. Then check for a play store update by hitting profile pic and then settings->about, check for update.