How are randomly large prime numbers chosen and proven to be prime?

in RSA, two random prime numbers are multiplied, but how is the first number chosen? i would guess just putting together 0s and 1s in binary and then testing the result, but how do you test it? if im wrong, then whats the answer to the first question?

How do programs/scripts that output prime numbers work (in pseudo-code please)?

whats the general idea to generating prime numbers? i know the 2^x-1 thing, but its useless if you cant test the number. and the square root trick is too time consuming for the computer