Here's how to match a prefix code (a + or (00), then a number from 1 to 1939, with an optional space):
This doesn't look for a valid prefix but something that might be a prefix. See the full list of prefixes
(?:00|\+)?[0-9]{4}
Then, as the entire phone number length is, at most, 15, we can look...