O 10001º número primo – Project Euler

Pessoal, passei o final de semana “brincando” com as questões do Project Euler. Consegui fazer a questão 7 e estou disponibilizando o código para quem quiser estudar ou procurar melhorá-lo.

Código antigo

#-*- coding: utf-8 -*-
#Programa encontra o 10001° número primo.
#Questão 7 do Project Euler - http://projecteuler.net/
#Autor: Luiz Augusto de M. Morais
#Data: 31/05/2010

from os import system

#função que mostra a porcentagem do carregamento
def carregando(atual, tamanho):
	system("clear")
	print "Carregando: (%1.1f%%)" % ((atual / float(tamanho)) * 100)

#funçao que identifica se o número é primo
def ehPrimo(n):
	#não existem primos menores que 2
	if (n < 2):
		return False
	#cinco primeiros números primos
	elif (n == 2 or n == 3 or n == 5 or n == 7 or n == 11):
		return True
	#segundo o Crivo de Erastótenes, os múltiplos de números primos não são primos
	elif (n % 2 == 0) or (n % 3 == 0) or (n % 5 == 0) or (n % 7 == 0) or (n % 11 == 0):
		return False
	#se nada der certo, ache do jeito mais simples
	else:
		count = 0
		#a lista começou de 11 porque os números anteriores já foram verificados
		for i in range(11, n):
			if (n % i == 0):
				count += 1
		if count == 0:
			return True
		return False

#programa principal
contador, numero = 0, 1

#o laço só para quando achar o 10001° número primo
while contador != 10001:
	numero += 1
	if ehPrimo(numero):
		carregando(contador, 10001) #mostra o andamento do programa
		contador +=1

print "O 10001º número primo é: %d" % (numero)

O tempo para este programa achar o número primo ainda está alto. Quem sabe, vocês não possam melhorá-lo.
Para saber quanto tempo o programa demorou para ser executado, digite no Terminal:

$ time python <nome_do_programa.py>

[ATUALIZADO 03/06/2010] Pessoal, eu mudei algumas coisinhas no código e consegui um aumento de 69% da performance do programa.

O programa anterior demorou 3m33.995s para achar o 10001º primo, enquanto que o atual encontrou em 1m4.795s.

Código atual

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from os import system

def isPrime(number):
	if number < 2:
		return False
	elif (number == 2) or (number == 3) or (number == 5)\
	or (number == 7) or (number == 11):
		return True
	elif (number % 2 == 0) or (number % 3 == 0) or (number % 5 == 0)\
	or (number % 7 == 0) or (number % 11 == 0):
		return False
	else:
		for i in range(11, (number + 1) / 2):
			if number % i == 0:
				return False
		return True

def loading(current, lenght):
	system("clear")
	print "Carregando: (%1.1f%%)" % ((current / float(lenght)) * 100)

count, number = 0, 1
while count != 10001:
	number += 1
	if isPrime(number):
		loading(count, 10001)
		count += 1
print number

Acesse o novo endereço do Olá Mundo!: http://ola-mundo.com