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 1000. This can be checked by finding the Hamiltonian cycles with backtracking). 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.

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$.

For larger $n$ such picture are less useful. For example for here is a picture for $n=100$.