Sequence of primes by trial division: Difference between revisions
Sequence of primes by trial division (view source)
Revision as of 21:09, 17 January 2023
, 1 year agoLFE version
(→OCaml: add) |
(LFE version) |
||
Line 1,960:
</syntaxhighlight>
More to see in [http://epsilonwiki.free.fr/lambdaway/?view=primes2]
=={{header|LFE}}==
This version is inspired by PicoLisp, however instead of using the algorithm from the paper "Lazy wheel sieves and spirals of primes", this program uses a static 2,3,5,7,11 factorization wheel. Since the diminishing returns of factor wheels hit hard after 11, it's arguably better to use a precomputed fixed sized wheel. Like the PicoLisp version, this code also uses a separate thread to serve the primes.
<syntaxhighlight lang="lisp">
(defmodule tdwheel
(export
(primes 0) (gen 1) (next 1)))
(defun +wheel-2x3x5x7x11+ ()
#B( 12 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2
4 14 4 6 2 10 2 6 6 4 2 4 6 2 10 2 4 2 12 10 2 4 2 4
6 2 6 4 6 6 6 2 6 4 2 6 4 6 8 4 2 4 6 8 6 10 2 4
6 2 6 6 4 2 4 6 2 6 4 2 6 10 2 10 2 4 2 4 6 8 4 2
4 12 2 6 4 2 6 4 6 12 2 4 2 4 8 6 4 6 2 4 6 2 6 10
2 4 6 2 6 4 2 4 2 10 2 10 2 4 6 6 2 6 6 4 6 6 2 6
4 2 6 4 6 8 4 2 6 4 8 6 4 6 2 4 6 8 6 4 2 10 2 6
4 2 4 2 10 2 10 2 4 2 4 8 6 4 2 4 6 6 2 6 4 8 4 6
8 4 2 4 2 4 8 6 4 6 6 6 2 6 6 4 2 4 6 2 6 4 2 4
2 10 2 10 2 6 4 6 2 6 4 2 4 6 6 8 4 2 6 10 8 4 2 4
2 4 8 10 6 2 4 8 6 6 4 2 4 6 2 6 4 6 2 10 2 10 2 4
2 4 6 2 6 4 2 4 6 6 2 6 6 6 4 6 8 4 2 4 2 4 8 6
4 8 4 6 2 6 6 4 2 4 6 8 4 2 4 2 10 2 10 2 4 2 4 6
2 10 2 4 6 8 6 4 2 6 4 6 8 4 6 2 4 8 6 4 6 2 4 6
2 6 6 4 6 6 2 6 6 4 2 10 2 10 2 4 2 4 6 2 6 4 2 10
6 2 6 4 2 6 4 6 8 4 2 4 2 12 6 4 6 2 4 6 2 12 4 2
4 8 6 4 2 4 2 10 2 10 6 2 4 6 2 6 4 2 4 6 6 2 6 4
2 10 6 8 6 4 2 4 8 6 4 6 2 4 6 2 6 6 6 4 6 2 6 4
2 4 2 10 12 2 4 2 10 2 6 4 2 4 6 6 2 10 2 6 4 14 4 2
4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 12 2))
(defun next (pid)
(! pid `#(next ,(self)))
(receive (x x)))
(defun primes ()
(spawn (MODULE) 'gen '((2 3 5 7 11))))
(defun gen (primes)
(receive
(`#(next ,sender)
(case primes
((list p)
(! sender p)
(divloop 1 0 (+wheel-2x3x5x7x11+)))
((cons p ps)
(! sender p)
(gen ps))))))
(defun divloop (n j wheel)
(receive
(`#(next ,sender)
(let [((tuple n' j') (next-prime n j wheel))]
(! sender n')
(divloop n' j' wheel)))))
(defun next-prime (n0 j wheel)
(let [
(n (+ n0 (binary:at wheel j)))
(j' (if (=:= j (- (byte_size wheel) 1))
0
(+ j 1)))
]
(if (td-prime? n 1 0 wheel)
(tuple n j')
(next-prime n j' wheel))))
(defun td-prime? (n d0 j wheel) ; 2,3,5,7,11 does not divide n
(let [(d (+ d0 (binary:at wheel j)))]
(cond
((> (* d d) n)
'true)
((=:= 0 (rem n d))
'false)
(else
(td-prime?
n
d
(if (=:= j (- (byte_size wheel) 1)) 0 (+ j 1))
wheel)))))
</syntaxhighlight>
Driver code:
<syntaxhighlight lang="lisp">
#!/usr/local/bin/lfescript
(defun show-primes (n)
(show-primes n (tdwheel:primes)))
(defun show-primes
((0 _) (io:format "~n"))
((n pid)
(lfe_io:format "~b " (list (tdwheel:next pid)))
(show-primes (- n 1) pid)))
(defun show-table (limit)
(io:format "n\tnth prime\n")
(show-table limit 1 1 (tdwheel:primes)))
(defun show-table (limit k goal pid)
(cond
((> k limit)
'ok)
((=:= k goal)
(let [(p (tdwheel:next pid))]
(io:format "~b\t~b\n" (list goal p))
(show-table limit (+ k 1) (* goal 10) pid)))
(else
(tdwheel:next pid) ; discard result
(show-table limit (+ k 1) goal pid))))
(defun main (_)
(show-primes 25)
(show-table 100000))
</syntaxhighlight>
{{Out}}
<pre>
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
n nth prime
1 2
10 29
100 541
1000 7919
10000 104729
100000 1299709
</pre>
=={{header|Liberty BASIC}}==
| |||