MITTutorialApril2009: histExercise.fss

component histExercise
import Set.{...}
export Executable

prime: Boolean[1000] = array1[\Boolean,1000\](true)
upper = prime.bounds.upper

removeMultiplesOf(p: ZZ32): () = do
    prime[i] := false, i <- p^2 : upper : p
end

sieve() = do
    prime[0] := false
    prime[1] := false
    prev: ZZ32 := 1
    rootRoot = |/ SQRT SQRT upper \|
    for p <- seq(2:rootRoot), prime[p] OR p = rootRoot do
        for p' <- (prev^2 + 1):(p^2 - 1), prime[p'] do
            removeMultiplesOf(p')
        end
        prev := p
    end
end

(* Define a hist function.
 * Given a set of primes, how many primes end with each digit?
 *  Input: A set of primes
 * Output: An array of size 10 where the i-th element of the array
 *         denotes the number of primes ending with i
 *
 * Hint 1: ZZ32[10] denotes an array type of size 10 with elements of type ZZ32
 * HInt 2: array1[\ZZ32,10\](0) creates a 1-dimensional array of size 10 with
 *         elements of type ZZ32 initialized with 0.
 * Hint 3: a set can be used as a generator in a for loop.
 * Hint 4: MOD is a Fortress modulo operator.
 *)
hist(primes: Set[\ZZ32\]): ZZ32[10] =
    fail("You still need to implement a hist function.")

(**********************************************************************************
 * TESTS
 **********************************************************************************)

run(): () = do
    sieve()
    result = hist {[\ZZ32\] p | (p, isPrime) <- prime.indexValuePairs, isPrime }
    assert(result[0],  0)
    assert(result[1], 40)
    assert(result[2],  1)
    assert(result[3], 42)
    assert(result[4],  0)
    assert(result[5],  1)
    assert(result[6],  0)
    assert(result[7], 46)
    assert(result[8],  0)
    assert(result[9], 38)
    println("Your hist appears to work.")
end

end