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$. See my comment for an explanation why odd is never possible.
It might seem plausible that the answer to your question could be: for the even n. (At least this is true for all $n$ up to 140). For a random graph with $O(n\log n)$ edges, the probability to contain a Hamiltonian cycle tends to $1$. If the edges you prescribe behave randomly for even $n$ and there are more of them, then the result seems plausible.
On the other hand, the edges might not behave randomly; in fact for $n=142$ and $n=146$ I couldn't find a cycle, and also no certificate that such a cycle does not exist. For $n\in\{144,148,150,152,154\}$ I could again find cycles. (This might just be my computer taking long on these instances...)
Of course this method can be adapted to simliar situation, when your are looking for the difference being prime or the sums belonging to some other set (e.g. fewer primes).
I attach a picture for the graph and the Hamiltonian cycle for $n=16$.
