Dan Asimov wrote (off-list, presumably to spare me the embarrassment I so richly deserve)

But don't the terms of the problem say the numbers are > 1 ?

Oh yeah, so they do. So what Scheherezade actually discovers from Petrouschka's first remark is that the number isn't of the form pq or p^2. -- g