Kind of a strange story. That prime number approach is just awful. You'll (obviously) need a bignum library. You need a prime number generator that can get you the Nth prime. The division operation is going to be very slow. It's interesting to consider how it works, but it would never occur to me to mention it since it's so clearly not actually a good idea.

If you want to take advantage of having a limited range of possible characters, just use a bit vector. If you're limited to ASCII then you only need 16 bytes to track them all. Less if you're limited to printable characters.

It would be fun to discuss the prime number version in a sort of "how would this work and why would it be terrible?" way, but if I had an interviewer present it as a way to "do better" I'd have to seriously reconsider if I'd actually want the job.

Technically, sure, you're absolutely right; but the moral of the story is (I think) that making your interviewer think you're an out-of-box thinker all but guarantees an offer.