Can you make your way through the Ulam spiral?
JavaScript (ES6), 169 bytes
Saved 1 byte thanks to @att
Expects (z)(x,y). Returns false if there's a solution or true otherwise.

z=&gt;F=(X,Y,i=z,k)=&gt;--i?[-1,0,1,2].every(d=&gt;(g=d=&gt;n%--d?g(d):d==1)(n=(k=2*Math.max(x=X+d%2,-x,y=Y+~-d%2,-y))*k-~(-y&lt;x?y-k-x:k+x-y))|F[k=[x,y]]||F(x,y,i,F[k]=1)|--F[k]):X|Y

This is fast enough for all existing test cases, but I guess it's likely to time out on some other ones.
Try it online!
Commented
NB: the spiral formula is similar to the one I used in my answer to Spiral neighbourhoods.
z =&gt;                              // outer function taking z
F = (                             // main recursive function taking:
  X, Y,                           //   (X, Y) = current position
  i = z,                          //   i = move counter initialized to z
  k                               //   k = local variable whose initial value is ignored
) =&gt;                              //
  --i ?                           // decrement i; if it's not equal to 0:
    [-1, 0, 1, 2].every(d =&gt;      //   for each direction d:
      ( g = d =&gt; n % --d ? g(d)   //     g is a recursive primality test function
                         : d == 1 //     which is invoked ...
      )(                          //
        n =                       //     ... on the 1-indexed square ID n defined as:
          ( k = 2 * Math.max(     //       k² + (k + x - y) * s + 1
              x = X + d % 2, -x,  //       with:
              y = Y + ~-d % 2, -y //         x = X + dx
            )                     //         y = Y + dy
          ) * k -                 //         k = 2 * max(|x|,|y|) = 2 * max(x,-x,y,-y)
          ~(-y &lt; x ? y - k - x    //         s = -1 if -y &lt; x or 1 otherwise
                   : k + x - y)   //
      )                           //     abort if n is prime
      | F[k = [x, y]]             //     or (x, y) was already visited
      || F(x, y, i, F[k] = 1)     //     otherwise mark (x, y) as visited and do a
                                  //     recursive call with the new position
      | --F[k]                    //     clear the mark afterwards
    )                             //   end of every()
  :                               // else:
    X | Y                         //   falsy if and only if X = Y = 0