While browsing the web, temperatures should not be this much high. Around 30-32 degree celsius is fine. While watching YouTube videos, a little bit increase is acceptable by 1 or 2 degrees.
And while gaming, well, it may reach 40 degrees, but it's normal.
I think some rogue app (if you have installed any since yesterday) in your phone may be causing these high temperatures even during normal usage. Monitor all the apps on your phone through battery monitor in battery settings. Also, I would suggest you to do a 'Wipe Cache Partition' from Recovery Menu.
This fixes most of such type of issues.
Even after that temperatures remain high, especially for normal usage, then do a hard Factory Reset via Recovery menu.
I have been using Note 4 for more than a year now. Sometimes, I also experienced this high temp. problem on Lollipop while carrying out normal tasks like browsing.
But Marshmallow fixed everything, it seems.
Since you have got your phone yesterday only, it must obviously be on Android Marshmallow.
Moreover, give it some time (a week or two) to settle