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

Published on 12 May 2024 09:40 PM
#Picolisp

How to resolve the algorithm Sequence of primes by trial division step by step in the PicoLisp 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 PicoLisp programming language

Source code in the picolisp programming language

(de prime? (N)
   (or
      (= N 2)
      (and
         (> N 1)
         (bit? 1 N)
         (let S (sqrt N)
            (for (D 3  T  (+ D 2))
               (T (> D S) T)
               (T (=0 (% N D)) NIL) ) ) ) ) )

(de primeseq (A B)
   (filter prime? (range A B)) )

(println (primeseq 50 99))

(de comma_fmt (N) (format N 0 "." ","))

(de prime-td? (N Chk)
   (let (D NIL  Rt (sqrt N))
      (loop
         (NIL Chk T) # if we run out of test divisors then it's prime.
         (setq D (pop 'Chk))
         (T (> D Rt) T)
         (T (=0 (% N D)) NIL))))

(de primes (Run?)
   (if (not Run?)
      (co 'primegen) # stop
      (co 'primegen
         (yield 2)
         (yield 3)
         (make
            (chain (3 1 2))  # start with W1 = 1, 3, 5, 7, 9, ...
            (loop
               # At the start of the loop, switch to the next size wheel.
               (let
                  ((Sj . Wheel) (made)  # current wheel (size & spokes)
                     P (cadr Wheel)     # current sieving prime
                     Sk (* P Sj) )      # size of next wheel
                  (made (list Sk))
                  (chain
                     (filter '((N) (n0 (% N P))) Wheel))
                  (for (O Sj (< O Sk) (+ O Sj))
                     (for W Wheel
                        (let N (+ O W)
                           (when (n0 (% N P))
                              (link N)
                              (when (prime-td? N (cdr Wheel))
                                 (yield N))))))))))))

(do 31 (prin (primes T) " ")) (prinl)
(primes NIL)
(do 10000 (primes T))
(prinl "The 10,001st prime is " (comma_fmt (primes T)))
(bye)

You may also check:How to resolve the algorithm Guess the number/With feedback step by step in the Brat programming language
You may also check:How to resolve the algorithm Variables step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Hash join step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Topological sort step by step in the Tcl programming language
You may also check:How to resolve the algorithm Exponentiation with infix operators in (or operating on) the base step by step in the Ada programming language