How to resolve the algorithm Sequence of primes by trial division step by step in the LFE programming language

Published on 12 May 2024 09:40 PM
#Lfe

How to resolve the algorithm Sequence of primes by trial division step by step in the LFE programming language

Table of Contents

Problem Statement

Generate a sequence of primes by means of trial division.

Trial division is an algorithm where a candidate number is tested for being a prime by trying to divide it by other numbers. You may use primes, or any numbers of your choosing, as long as the result is indeed a sequence of primes. The sequence may be bounded (i.e. up to some limit), unbounded, starting from the start (i.e. 2) or above some given value. Organize your function as you wish, in particular, it might resemble a filtering operation, or a sieving operation. If you want to use a ready-made is_prime function, use one from the Primality by trial division page (i.e., add yours there if it isn't there already).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sequence of primes by trial division step by step in the LFE programming language

Source code in the lfe programming language

(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)))))


#!/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))

You may also check:How to resolve the algorithm The Twelve Days of Christmas step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Dice game probabilities step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Caesar cipher step by step in the Scala programming language
You may also check:How to resolve the algorithm Maximum triangle path sum step by step in the Sidef programming language
You may also check:How to resolve the algorithm Yin and yang step by step in the Dart programming language