Claramente, Python é a linguagem errada para o Project Euler Experimentem um dos descendentes da APL, como J ou K, que são linguagens extremamente rápidas (e sucintas, ou não descendessem de APL) construídas propositadamente para manipulação matemática de grandes volumes de dados e com grande precisão.
Usar Python, J, K or whatever linguagem de programação não tem grande importância para o one-minute rule!
Na realidade se o programa acima é lento não é culpa do Python, mas sim do algoritmo. Programar o mesmo algoritmo em J ou em C não iria adiantar nada.
Aliás é por isso que o Python até é uma boa linguagem para o projecto Euler porque te permite testar diferentes algoritmos minimizando o tempo que gastas a escrever os programas - isso é mais importante do que minimizar o tempo de execução, quando estás à procura do melhor algoritmo.
Como tinha dito ontem, em qualquer problema do ProjectEuler, há sempre uma maneira matemática de reduzir (e bastante!!) o número de casos a testar.
Para este caso particular, do universo que queremos testar (os números todos até 10**9 ,exclusive) podemos reduzir em muito este número já que: