Início > Códigos-Fonte, Dicas, Python > O 10001º número primo – Project Euler

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

  1. Reg glob
    23 de junho de 2010 às 22:17

    Olá,
    acredito que você possa otimizar ainda mais o seu programa, tente tirar a raiz quadrada do número que você está testando, pois se um número não é primo no pior dos casos ele será o quadrado de outro número. Boa sorte e divirta-se!

    • 25 de junho de 2010 às 09:59

      Valeu pela dica Reg glob, vou fazer isso.
      Só uma coisa, o endereço do blog mudou. Se quiser ver novos posts, acompanhe pelo endereço: http://ola-mundo.com

      Até mais!

  2. André Luis
    21 de julho de 2010 às 10:46

    nessa linha: for i in range(11, (number + 1) / 2): não entendi o motivo do / 2.
    Fiz sem ele em um programa delphi e o resultado foi quase instantâneo, pode ser isso que está atrasando o seu programa:
    Se o number for 12, ao chegar nessa linha ele vai dar um for de 11 até 6,5 ????

  3. 22 de julho de 2010 às 22:21

    André, primeiramente, gostaria de informar que este blog não está mais sendo atualizado, se você quiser continuar acompanhando as novidades do blog, acesse o novo domínio: http://ola-mundo.com.

    Com relação ao código, o primeiro parâmetro é 11 porque existem testes anteriores que fazem com que o número sempre seja maior que 11.

    Segundo, a variável number nunca será par, pois existe uma condição anterior que elimina todos os números pares, logo, um número (ímpar +1) sempre será par, então, a expressão: (number + 1)/2 será sempre um valor inteiro.

    elif (number % 2 == 0) or (number % 3 == 0) or (number % 5 == 0) or (number % 7 == 0) or (number % 11 == 0):
    return False

    O trecho de código acima faz com que, se a variável numero for múltiplo de algum desses elementos, a função pare e retorne o valor False.

    Com relação ao desempenho do programa, você disse que o programa que você fez em Pascal (Delphi) executou mais rápido. Isso ocorreu porque o Pascal é uma linguagem compilada, em contrapartida, o Python é interpretado, o que deixa o programa muito mais lento.

    Este meu programa ainda está muito mal feito, sei que ele tem muito o que melhorar.
    Agradeço a sua participação no blog, André. Aproveite e continue nos acompanhando pelo novo endereço (http://ola-mundo.com).

  1. No trackbacks yet.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: