Calculando numeros primos em python

Este post surge inicialmente à partir do Project Euler: Diversão com programação e matemática, calculando números primos. Guardei a notícia no google reader e hoje estive lendo o site do José Lopes de Oliveira Júnior mais especificamente neste link sobre calculo de numeros primos, no exemplo é citado o "Crivo de Eratóstenes".

Fuçando na web achei um código que quero melhorar com a ajuda dos nobres leitores e saber se ele se enquadra na definição do Crivo de Eratóstens. Segue o código:

Obs: Nos comentários do post original -->>; Dica: use o crivo de eratóstenes. Dá pra fazer a solução rodar em menos de 1 segundo.

Veja este post.

Um comentário:

Cacilhας, La Batalema disse...

$ cat vivaotux.py
# coding: UTF-8
print [x for x in range(2, 10000) if not [t for t in range(2,x) if not x%t]]

$ time python vivaotux.py >/dev/null

real 0m7.305s
user 0m7.184s
sys 0m0.008s

$ cat eratostenes.lisp
(defun primes ((*max* integer))
  (loop
    for i from 2 to *max*
    with primes = '()
    if (not (let ((*last* (ceiling (sqrt i))))
             (loop
              for j in primes
              while (<= j *last*)
              if (= (mod i j) 0)
              do (return t))))
    do (setq primes (append primes (list i)))
    finally (return primes)))


(defun main ()
  (progn
    (format t "~A~%" (primes 10000))))

(main)

$ time clisp eratostenes.lisp >/dev/null

real 0m0.142s
user 0m0.124s
sys 0m0.016s

$ cat eratostenes.py
# coding: UTF-8

from math import ceil, sqrt
primes = []
for i in xrange(2, 10000):
    is_prime = True

    for e in primes:
        if e > (ceil(sqrt(i))):
            break
        if i % e == 0:
            is_prime = False
            break
    
    if is_prime:
        primes.append(i)

print primes

$ time python eratostenes.py >/dev/null

real 0m0.041s
user 0m0.036s
sys 0m0.004s

[]’s
Cacilhας, La Batalema

linux-cookbook

Grupos do Google
Participe do grupo linux-cookbook
E-mail:
Visitar este grupo