10 Apr 2010

Project Euler: Diversão com programação e matemática, calculando números primos

Olá pessoal!

Quem me acompanha pelo Twitter (InFog9) viu que eu comecei a brincar com os problemas matemático/computacionais do Project Euler. Pois bem, o primeiro problema que eu resolvi foi o 7º, a ideia dele é encontrar o 10001º número ímpar, o que não é exatamente muito complexo, mas dependendo do algoritmo empregado pode exigir mais tempo de processamento.

A primeira solução que eu fiz foi essa:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Problem 7
# http://projecteuler.net/index.php?section=problems&id=7
#
# Solved by Evaldo Junior
# April, 8th - 2010
#
def isPrime(number):
if (number < 2):
return False
elif (number == 2):
return True
else:
for i in range(2, number):
if (number % i == 0):
return False
return True

def main():
totalCount, totalPrime = 0, 0
while (totalPrime < 10001):
totalCount += 1
if (isPrime(totalCount)):
totalPrime += 1
print('The 10001st prime number is: %i' % (totalCount))

if __name__ == "__main__":
main()

Rodando isso em um Intel Dual Core 4400@2.00GHz com 1GB de ram o tempo de processamento foi esse:

2m49.673s

Caramba! Quase três minutos!

Aí durante a reunião do GCCSD, conversando com o Kretcheu sobre os problemas do Project Euler ele disse que a maneira que eu usei a mais confiável, pois a tentativa e erro é o método mais confiável para determinar se um número é primo ou não. Então eu tive umas ideias, e até comentei com ele, para reduzir esse tempo. A primeira ideia é: se o número for par, nem chama o algoritmo, a segunda ideia é parar o algoritmo ao chegar na metade das tentativas do número sendo testado (se o número for 301, então parar em 151).

Vamos ver como fica o tempo de execução com o algoritmo melhorado:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Problem 7
# http://projecteuler.net/index.php?section=problems&id=7
#
# Solved by Evaldo Junior
# April, 8th - 2010
#
# Updated April, 10th - 2010
#
def isPrime(number):
if (number < 2):
return False
elif (number == 2):
return True
elif (number %2 == 0):
return False # If number is even
else:
for i in range(2, number / 2):
if (number % i == 0):
return False
return True

def main():
totalCount, totalPrime = 0, 0
while (totalPrime < 10001):
totalCount += 1
if (isPrime(totalCount)):
totalPrime += 1
print('The 10001st prime number is: %i' % (totalCount))

if __name__ == "__main__":
main()

E o resultado:

0m58.333s

Agora sim, só com pequenas mudanças o algoritmo rodou quase DOIS minutos mais rápido, ou seja, o segundo algoritmo levou apenas 34% do tempo que o primeiro algoritmo levou. Estou começando a gostar deste algoritmo =). mas vamos em frente!

Agora vou considerar o seguinte: Se o número não é par, então ele não pode ser dividido por 2, então não vou tentar a divisão por outros pares, ou seja, agora o algoritmo incrementa a variável i de dois em dois e é iniciada em 3 e não mais em 2:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Problem 7
# http://projecteuler.net/index.php?section=problems&id=7
#
# Solved by Evaldo Junior
# April, 8th - 2010
#
# Updated April, 10th - 2010
#
def isPrime(number):
if (number < 2):
return False
elif (number == 2):
return True
elif (number %2 == 0):
return False # If number is even
else:
for i in range(3, number / 2, 2):
if (number % i == 0):
return False
return True

def main():
totalCount, totalPrime = 0, 0
while (totalPrime < 10001):
totalCount += 1
if (isPrime(totalCount)):
totalPrime += 1
print('The 10001st prime number is: %i' % (totalCount))

if __name__ == "__main__":
main()


O resultado? Olha só:

0m27.380s

Menos da metade do tempo que o algoritmo anterior!

Bem, agora chega. Quem sabe depois eu melhoro o esse algoritmo de calcular os primos e consigo chegar em na casa dos 10 segundos?

Quer tentar também? Acesse o site do Project Euler, veja os problemas e boa sorte!

UPDATE

Eu esqueci de falar como eu faço para medir o tempo de execução dos scripts... Para fazer essa medição eu uso o comando time, veja um exemplo:

$ time ./script.py

Valeu por perguntar, Guido.

InFog