Iterate over the diagonals of the matrix and check for each element.

Check if the element is prime or not in O(sqrt(n)) time.