@mustbejones, yes, 01133 for France and 01134 for Spain if you are dialing from the US. And in my experience, smartphones, at least, do understand a "+" in front of a number and will dial accordingly. I have been traveling between the US and France for a decade and my contacts have always been coded with a "+", and that way, I don't have to think about the issue, I just call that particular person/business and the phone takes care of the international dialing prefix (or not) for the country I'm in, and whether to drop leading zeroes from phone numbers (or not).
So, as an example, I can have a contact in the States with the phone number coded as "+1 (212) 555-1212". When I am in the States, but not in New York City, the phone just dials 12125551212. If I am in New York City, the phone just dials 5551212. If I am in France, the phone dials 0012125551212. I can also have a contact in France coded as "+33 (0)5 51 50 10 15" and when I dial that number in France it dials 0551501015, but in the US it dials 01133551501015. Magic