I haven't solved it yet, but it seems to be solvable by sheer diligence? Is there a faster solution? I think in an interview I would ask to write a computer program that solves it. Wait - I guess now I have to try that :-(
Edit: which programming language has good support for primes? I thought I saw one recently, but can't find it now.