battousai said:
I'm looking for the 2nd type of book (for math majors).
I would say then the Dudley book is most approachable, especially for self study. Its a Dover book, so it can be had for cheap.
I took number theory as an undergrad over the summer and we used an absolutely horrendous book (but at least is was free:
http://www.shoup.net/ntb/ ) and I had the Dudley book the whole time, but never bothered to read it for the better part of the session until the last couple of weeks when, I then realized that I would have gotten much much more out of my course had I used that book for the bulk of my studying. Everything that I was left in a fog with was immediately cleared up by the Dudley book. Plenty of exercises, answers to exercises, etc.
I think its worth picking up, even if after reading some of it, you feel its not rigorous enough (I don't feel that way, I think its perfect for a first intro to the subject) and you need a more challenging book, at least you'll get your feet wet and won't spend much cash to do it.
Personally, I would love to learn more and might move on to some of the books suggested by xristy. I am personally looking at picking up Apostol's book.