Let's say you want "n" to be 2048 bits (RSA 2048). Then "p" and "q" would each be 1024 bits.
The computer generates a random 1024 bit number (almost instantaneous) and tests it for primality. There are different kinds of primality tests, most of them are statistical. They are very fast (I know this is not quantified, but I work on embedded microcontrollers running at 100MHz with no cache, so I have no idea about speed on desktop).
So generating a bunch of 1024 bit numbers, finally you'll hit one that passes multiple iterations of primality tests. (not going into the details here about the statistics and what is "good enough", it's all easy enough to find). Do the same to get your "q", multiply them, you have your modulus "n". "n" plus your "e" (probably 65537) are your public key.
As you can imagine, prime density decreases as the numbers get bigger; there are ways to estimate prime density based on the size of the prime you are trying to generate. 40% of numbers under 10 are prime, but only 25% density for numbers under 100, and even less for 1024-bit numbers. If I recall correctly, on average, you'll have to try the generate/primality test cycle ~360 times to find a 1024-bit number that tests as prime. It's not thousands or millions. And for 512 bit numbers it's probably under 100 attempts.
Because the number space 2^1024 is so huge, it's incredibly unlikely that your p & q will match anyone else's. In fact, each of those 1024 bit strings have probably never existed on any computer in the history of the earth.
I hope that gives you enough of a sense of how it works. It's basically that simple. I've omitted some details, discussion of strong primes, etc. because it gets into details that are outside the scope of your question.
