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.
Assinar:
Postar comentários (Atom)
linux-cookbook
|
| Participe do grupo linux-cookbook |
| Visitar este grupo |
$ cat vivaotux.py
ResponderExcluir# 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