How costly is to find millions of large prime numbers for RSA?
Yes, this is doable.  Here is a construction, built out of several basic primitives:


Let $R$ be a randomized  primality generation algorithm; there are many of them.

It uses randomness, so let's make the bits of randomness it uses explicit as input: $R(c)$ is the output it produces, when given a random number generator that outputs the random bits $c$.
Let $G$ be a cryptographically secure pseudorandom generator: something that stretches a short seed (key) to a long pseudorandom output.  You could use AES in CTR mode, or any stream cipher, for this.
Let $H$ be a cryptographic hash function, e.g., SHA256.


Now, to element $x$, you can assign the prime number $R(G(H(x)))$ to $x$.  It's as simple as that.

This is a deterministic algorithm that will assign a prime to each element, and always assign the same prime to each possible element.  Also, if you generate primes from a large enough range, then the primes will almost surely be distinct.  For instance, if you generate 256-bit primes, then by the birthday paradox, it is essentially guaranteed that all the primes will be distinct (the chances that two different elements $x,x'$ is exponentially small, and negligible in practice).