2 added 607 characters in body

Haskell, 7979 74 bytes (thanks to Laikoni)

72 bytes as annonymus function (the initial "f=" could be removed in this case).

f=(!)(-1);n!x|x>1,all((>0).mod x)[2..x-1]=x|y<-x+n=last(-n+1:[-n-1|n>0])!y


Try it online!

f=(!)(-1);n!x|x>1&&all((>0).mod x)[2..x-1]=x|1>0=(last$(-n+1):[-n-1|n>0])!(x+n)  Try it online! Explanation: f x = g (-1) !x isPrime x = x > 1 && all (\k -> x mod k /= 0)[2..x-1] n!x | isPrime x = x -- return the first prime found | n>0 = (-n-1)!(x+n) -- x is no prime, continue with x+n where n takes the | otherwise = (-n+1)!(x+n) -- values -1,2,-3,4 .. in subsequent calls of g(!)  Haskell, 79 bytes f=(!)(-1);n!x|x>1&&all((>0).mod x)[2..x-1]=x|1>0=(last$(-n+1):[-n-1|n>0])!(x+n)


Try it online!

Explanation:

f x = g (-1) x

isPrime x = x > 1 && all (\k -> x mod k /= 0)[2..x-1]
n!x | isPrime x = x            -- return the first prime found
| n>0       = (-n-1)!(x+n) -- x is no prime, continue with x+n where n takes the
| otherwise = (-n+1)!(x+n) -- values -1,2,-3,4 .. in subsequent calls of g


Haskell, 79 74 bytes (thanks to Laikoni)

72 bytes as annonymus function (the initial "f=" could be removed in this case).

f=(!)(-1);n!x|x>1,all((>0).mod x)[2..x-1]=x|y<-x+n=last(-n+1:[-n-1|n>0])!y


Try it online!

f=(!)(-1);n!x|x>1&&all((>0).mod x)[2..x-1]=x|1>0=(last$(-n+1):[-n-1|n>0])!(x+n)  Try it online! Explanation: f x = (-1)!x isPrime x = x > 1 && all (\k -> x mod k /= 0)[2..x-1] n!x | isPrime x = x -- return the first prime found | n>0 = (-n-1)!(x+n) -- x is no prime, continue with x+n where n takes the | otherwise = (-n+1)!(x+n) -- values -1,2,-3,4 .. in subsequent calls of (!)  1 Haskell, 79 bytes f=(!)(-1);n!x|x>1&&all((>0).mod x)[2..x-1]=x|1>0=(last$(-n+1):[-n-1|n>0])!(x+n)


Try it online!

Explanation:

f x = g (-1) x

isPrime x = x > 1 && all (\k -> x mod k /= 0)[2..x-1]
n!x | isPrime x = x            -- return the first prime found
| n>0       = (-n-1)!(x+n) -- x is no prime, continue with x+n where n takes the
| otherwise = (-n+1)!(x+n) -- values -1,2,-3,4 .. in subsequent calls of g