Another implementation using NestWhile:
```
f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], !PrimeQ[# - p] &] - p;
f[857]
f[859]
(*167*)
(*7333*)
```