After a lot of slogging, I've at last completed this puzzle. The ending is a bit of an anti-climax, because I don't see any interesting patterns in the final grid.
I didn't find it necessary to use Euclid's formula, though this was because I just did brute calculations on Excel. My starting point was 9d, where either P or X have to be 2. Why? well, the two numbers in the ratio can't both be even, as this would mean that the ratio isn't in its lowest terms. Also, the two numbers can't both be odd. The reason for this is that an odd number can be written as 2n+1, and its square is therefore 4n^2+4n+1. It has a remainder of 1 when divided by 4. Adding two odd squares together will give a number that has a remainder of 2 when divided by 4. Adding two odd numbers together will give an even number. However, dividing an even square by 4 will leave a remainder of 0 (an even number is 2n so its square is 4n^2). So we can't have two odd numbers in the ratio. That means that one of the numbers is odd and the other is even. This is of course consistent with Euclid's formula.
So either P or X^2 is even, but the only even prime is 2. But P cannot be 2, as no squares of non-zero positive integers differ by 4 (the squares of 0 and 2 differ by 4, but 0 is not a possible value). Hence X^2 is even, which implies that X is 2 and X^2 is 4. The only squares that differ by 4^2 = 16 are 3^2 = 9 and 5^2 = 25, so P = 3.
I was able to identify all 26 letters from 19 clues, with the other 23 clues confirming that the letters had been identified correctly. The key is to attack the clues in an efficient sequence, where you are adding at most two extra letters to those where you already have either a unique answer or at worst a very limited range of possibilities.