This is pretty WTF, but honestly your years of PHP experience are probably inversely proportional to your skill at this problem. All you really need is math -- its easier to do this by hand with a calculator than code it. My guess would be that php expertise is anti-correlated with remembering prime factorizations, no offense to php devs.