You are right, the number of primes lower than a given number is fixed... the thing is, even being fixed, there are still A LOT of prime numbers for the numbers we're taling about.
If we use a 1024 RSA Key we are talking about 2^1024 and that's ... well, a lot, so let's say (and this is just a guess, could be more or less, I have no idea), that one every 16 million consecutive number is a prime, and let's say 16 million is 2^24... then you have to test with 2^1000 primes ... which is the hell of a loop...
So, yeah, the number of primes below a given number is fixed but fixed doesn't mean few...