Question: Sampling from discrete power law distribution

I have got a discrete power law distribution from which I would like to sample.
I tried to define a new distribution, but didn't succeed so far.
The probability p(k) = C(gamma)*k^(-gamma),

With ProbabilityTable I've got the problem that my distribution is not limited to a certain range. It starts from a lower limit kmin, but goes to infinity.

I tried also with a piecewise function and then Distribution.

f:=piecewise(k>=kmin and k::integer, k^(-lambda)/ZetaII(lambda,kmin),0);
ND:=Distribution(PDF = unapply(f,k));
X:=RandomVariable(ND);
Sample(X,5);

But that also didn't work.

The only thing I can think of it to sample i from a DiscreteUniform distribution from kmin to infinity and j from a Uniform distribution from 0 to 1. If j<f(i) then I keep the sample, otherwise I sample again. But because of the power law nature (with its long tail) this is very, very inefficient.

I hope you can help me with a more efficient way.