I am not quite sure what notation of cycles you use, but to investigate this question for small $n$ you could do the following. Build a graph $G$ with vertices $1,\dots,n$ and edges $\{i,j\}$ whenever $i+j$ is prime. Then you seem to be looking for Hamiltonian cycles in that graph. Here is what you get for some small n:

    n
    4 [1, 2, 3, 4]
    6 [1, 4, 3, 2, 5, 6]
    8 [1, 2, 5, 8, 3, 4, 7, 6]
    10 [1, 4, 7, 10, 3, 2, 9, 8, 5, 6]
    12 [1, 10, 3, 8, 11, 12, 7, 6, 5, 2, 9, 4]
    14 [1, 10, 3, 2, 5, 14, 9, 8, 11, 12, 7, 4, 13, 6]
    16 [1, 12, 7, 16, 15, 14, 9, 8, 5, 2, 11, 6, 13, 10, 3, 4]
    18 [1, 18, 11, 8, 15, 16, 13, 6, 7, 12, 17, 2, 5, 14, 9, 10, 3, 4]
    20 [1, 2, 9, 10, 3, 20, 11, 8, 5, 18, 19, 12, 17, 14, 15, 16, 7, 6, 13, 4]
    22 [1, 2, 9, 22, 7, 4, 15, 8, 3, 10, 13, 16, 21, 20, 17, 14, 5, 6, 11, 18, 19, 12]
    24 [1, 10, 3, 20, 23, 14, 9, 4, 7, 12, 19, 24, 13, 16, 21, 22, 15, 8, 5, 2, 17, 6, 11, 18]
    26 [1, 16, 25, 12, 5, 14, 15, 22, 9, 8, 3, 26, 21, 20, 23, 24, 17, 2, 11, 6, 13, 18, 19, 4, 7, 10]
    28 [1, 18, 23, 24, 19, 4, 27, 2, 17, 14, 15, 26, 11, 8, 5, 12, 7, 16, 21, 22, 25, 28, 9, 20, 3, 10, 13, 6]
    30 [1, 16, 13, 18, 23, 20, 3, 10, 27, 26, 15, 8, 29, 30, 11, 2, 21, 22, 9, 28, 25, 12, 5, 14, 17, 24, 19, 4, 7, 6]
    32 [1, 16, 21, 2, 17, 14, 29, 30, 31, 6, 7, 22, 25, 28, 15, 26, 3, 10, 13, 4, 27, 32, 5, 8, 9, 20, 23, 24, 19, 12, 11, 18] 

So for small even $n$ there always seem to be such strings, and for no small odd $n$. It might seems plausible that the answer to your question could be: *for the even n*. (At least this is true for all $n$ up to 100)