Badly designed from the get-go... each server should only serve multiples of different primes...
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...