Most importantly, the first 6 digits of a Visa numer constitute a "BIN" (Bank Identification Number). I have heard that MasterCard uses variable number of digits for BIN, but I don't have proof. Some places will have lists of BINs (there's really not that many) and reject "card numbers" that don't have a correct BIN.
Secondarily, MasterCard numbers start with "51", "52", "53", "54" or "55". AmEx starts with "34" or "37", and Discover Cards start with "6011" or "650".
Generating a good "fake" CC number is a bit more complex than the first digit, and getting the Luhn checksum correct.
One of the other commentors is correct in having a huge number of checks around the format of a "credit card number". In practice, all kinds of rubbish ends up in the card number field, and every once in a while, it will pass the Luhn checksum and cause problems down stream.