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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Problem 7
# http://projecteuler.net/index.php?section=problems&id=7
#
# Solved by Evaldo Junior <junior@casoft.info>
# 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:

1

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Problem 7
# http://projecteuler.net/index.php?section=problems&id=7
#
# Solved by Evaldo Junior <junior@casoft.info>
# 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:

1

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Problem 7
# http://projecteuler.net/index.php?section=problems&id=7
#
# Solved by Evaldo Junior <junior@casoft.info>
# 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ó:

1

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:

1	$ time ./script.py

Valeu por perguntar, Guido.

InFog

15 Comentários

Autor: InFog
Publicado: abr 5th, 2010
Categoria: Desenvolvimento, python
Um Comentário

Problema de lógica: Crescimento populacional

Tags: Desenvolvimento, exercício, python

Olá pessoal!

Esses dias recebi um e-mail, do Diego Rodrigues, pedindo uma ajuda em Python. Ele mandou alguns probleminhas bem interessantes, mas a maioria relacionada à lógica e não a alguma sintaxe específica do Python.

Pois bem, dentre os problemas que ele enviou tinha um bem legal, veja o enunciado:

Supondo que a população de um país A seja da ordem de 80000 habitantes com uma taxa anual de crescimento de 3% e que a população de B seja 200000 habitantes com uma taxa de crescimento de 1.5%. Faça um programa que calcule e escreva o número de anos necessários para que a população do país A ultrapasse ou iguale a população do país B, mantidas as taxas de crescimento.

Agora a solução em Python que eu mandei para ele:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Problema de crescimento populacional
# Desenvolvido por Evaldo Junior (InFog)
# http://infog.casoft.info
popA, popB, anos = 80000, 200000, 0
cresA, cresB = 0.03, 0.015 # Crescimentos de 3% e 1,5% ao ano
while (popA < popB):
anos += 1
popA = popA + (popA * cresA)
popB = popB + (popB * cresB)
print("Após %i anos o país A ultrapassou o país B em número de habitantes." % anos)
print("País A: %.0f" % popA)
print("País B: %.0f" % popB)

Aqui o resultado foi:

Após 63 anos o país A ultrapassou o país B em número de habitantes.
País A: 515033
País B: 510964

O legal é que dá para fazer o programa mostrar o crescimento ano a ano e, quem sabe, gerar até um gráfico para ilustrar melhor.

E então, quem propõe uma solução diferente em Python ou mesmo em outras linguagens? Basta comentar.

InFog

1 Comentário

Autor: InFog
Publicado: mar 30th, 2010
Categoria: Blog, PHP, Tutoriais, python
3 Comentários

Expressões Regulares: Casar textos entre chaves

TAGS: None

Olá, pessoal!

Hoje vou mostrar uma dica bem legal, como casar textos entre chaves usando expressões regulares.

A necessidade surgiu de um amigo, o Rogério, e eu resolvi buscar uma solução.

Para o exemplo vou utilizar a string “ola, {sou} uma string com {varios} caracteres {especiais}”.

A ideia aqui é que o retorno seja composto pelos textos “{sou}”, “{varios}” e “{especiais}”.

Então vejam a solução em PHP:

1
2
3
4

$pattern = '/\{.*?\}/';
$text = "ola, {sou} uma string com {varios} caracteres {especiais}";
preg_match_all($pattern, $text, $result);
print_r($result);

O resultado seria:

1
2
3
4
5
6
7
8
9

Array
(
[0] => Array
(
[0] => {sou}
[1] => {varios}
[2] => {especiais}
)
)

Isso mesmo, um array com cada resultado em um ítem.

Agora uma solução em Python:

1
2
3
4
5
6
7
8

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import re
pat = re.compile('\{.*?\}')
text = "ola, {sou} uma string com {varios} caracteres {especiais}"
results = re.findall(pat, text)
for result in results:
print(result)

O resultado seria:

{sou}
{varios}
{especiais}

No Python foi necessário utilizar o módulo re para tratamento das expressões regulares.

Então, essa foi a dica de hoje. Alguém quer mostrar a solução em outra linguagem, ou melhorar as propostas? É só comentar.

InFog

3 Comentários