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:

  1. $ 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

    ResponderExcluir

Insira seu comentário - O mesmo será submetido à aprovação!

linux-cookbook

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