Sequence of primes by trial division: Difference between revisions
Content added Content deleted
(→OCaml: add) |
(LFE version) |
||
Line 1,960: | Line 1,960: | ||
</syntaxhighlight> |
</syntaxhighlight> |
||
More to see in [http://epsilonwiki.free.fr/lambdaway/?view=primes2] |
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}}== |
=={{header|Liberty BASIC}}== |