Primes

As a reactive program, this is quite degenerate: when started, it expects a positive integer n>2 as command line argument. It computes all primes smaller than or equal to n, prints the number of such primes to stdout and terminates.

The algorithm used illustrates imperative programming using updatable arrays in Timber. Here is the program:

module Primes where

import POSIX 

root = newRoot primes

primes env = class
   limit :: Int
   limit = fromRight (parse (env.argv!1))
   primesBound = limit `div` log3 limit

   primes := uniarray primesBound 0
   count  := 0

   isPrime k = loop 0
      where loop n = do 
              p = primes!n
              if p*p > k then
                 result True
              elsif k `mod` p  == 0 then
                 result False
              else loop (n+1)

   checkFrom k = do
     p <- isPrime k
     if p then 
        primes!count := k
        count := count + 1
     if k < limit then checkFrom (k+1)

   result action
     primes!0 := 2
     count := 1
     checkFrom 3
     env.stdout.write (show count++"\n")
     env.exit 0

log3 n  
  | n < 3       = 0
  | otherwise   = 1 + log3 (n `div` 3)
  

• Prime numbers are stored in array primes, which is initialised with all zeros (primitive function uniarray creates an array, whose size is given by the first argument, where all elements are initialised to the value of the second argument).
• The root action notes that 2 is a prime and initiates count to 1; it then checks numbers for primeness, starting with 3 in procedure checkFrom. This check is expressed using recursion, checking for successive numbers up to limit.

We note also that the correctness of the program depends on two mathematical facts:

• To limit the size of the array, the program uses the moderately clever bound that the number of primes up to n is at most n `div` log3 n.
• The procedure isPrime works by trial division, using already discovered primes: to check whether k is a prime, one tries to find a proper prime factor p such that p*p <= k. If none is found, k is prime. Thus it is important, if k is actually a prime, that a prime p with p*p > k exists to terminate the search. By Bertrand's postulate, much more is true: there is a prime with 2*p > k.