Well if n is a huge integer then generating a list of {n, n - 1, n - 2, ... 0} is of course going to exhaust memory. You could try something like this
p1000000 = Prime[1000000]
(* Can optimize to only check from Sqrt[n] *)
(n = p1000000; While[Mod[p1000000, n - 2] != 0, n = n - 2]; n - 2) // AbsoluteTiming
(* {6.72053, 1} *)
(n = p1000000 - 2; While[Mod[p1000000 - 2, n - 2] != 0, n = n - 2]; n - 2) // AbsoluteTiming
(* {6.75608, 910933} *)
Mod[p1000000 - 2, 910933]
(* 0 *)
If n is large, you are going to have to wait a long time. You could split the range and parallelize across available kernels, but still. You can probably estimate roughly how long it is going to take by computing the time to divide n by 1000 candidate divisors and extrapolating.
