Yo había pensado generar el array de primos y en lugar de barajar el array y después asignarlo a cada posición de la matriz, asignar a cada posición de la matriz una posición aleatoria del array de primos (entre 0 y 23) y así no desordenas el array de primos.
No tiene importancia... la próxima vez, que barajes te llega el array tal como quedó desordenado la vez previa, se vuelve a barajar... nunca se precisan en su orden estricto, luego carece de importancia. La ventaja es que de este modo te basta un único array, no dos.