[ATUALIZADO] Calculando números primos em Python

Ontem na unip rolou uma conversa de como descobrir se um número é perfeito ou primo. O pessoal sugeriu formas mais simples, do tipo dividir um número por TODOS os anteriores a eles, se for qualquer um for divisivel então ele não é primo.
Mas apesar dos resultados rápidos que obtemos, é possível usar um método ainda mais eficiente. Se um número não é primo ele tem um divisor primo menor ou igual a sua raiz quadrada, logo:

(se estiver vendo do Google reader, talvez não conseguirá ver o código)  
ATUALIZAÇÃO: 
Você também pode usar o teorema de Fermat para descobrir se um número é primo, o problema é que ele "deixa" escapar alguns números não-primos como se fossem, mas são muito poucos e o teorema é muito útil se você estiver calculando um número muito grande: