Just in case this is not a joke comment: If X is your prime base, and Y is the multiple, and Y is also prime, then you can't guarantee that one server won't have Y as it's prime base and X as the multiple. Not unless each server implements an `is_prime(N)` function for each new key, which brings us into the realm of quantum computing...
Umm, if X is prime and Y is a multiple of X, then Y is *not* prime, by definition...
Oh wait, I believe I understand you better now!
Example: First server serves multiples of 2, second server serves multiples of 3, they'll both try to serve 6... so really to make this foolproof, each server should only serve powers of distinct primes... that way there won't be collisions...