Prime Number.
A
'Prime Number' is a natural number greater than 1 that has no proper divisors other than 1 and itself.
The
Natural Numbers are 0, 1, 2, 3, 4, ....
The list of
prime numbers starts with 2, 3, 5, 7, 11, 13, .... Except for 2, all of these are odd, of course.
Haskell Implementation for Prime Number Test.
1. Let's define
divides function.
It should check if number m divides n, and this is true when and only when remainder of dividing n by m equals 0. The definition of
divides function can therefore be phrased in terms of a predefined function
rem for finding the remainder of a division process:
divides m n = ((rem n m) == 0)
in Haskell, symbol '=' is used for "is defined as" and symbol '==' for identity relation (and operator). Single apostrophes are used in this phrase only for showing terminal symbols boundaries. Terminal symbol is single "word" in "programming language", from which no other "words" can be produced, so it's not a "definition" or "production". For more details, please read Literature about languages and compilers.
A line of Haskell code of the form: foo t = .... (or: foo t1 t2 = .... , or: foo t1 t2 t3 = .... , and so on) is called a Haskell equation. In such an equation, foo is called the
function and t its
formal argument (or: t1 t2 t3 its
formal arguments).
Thus, in the Haskell equation: divides m n = ((rem n m) == 0) , divides is the function, m is the first formal argument, and n is the second formal argument.
2. Let's test
'divides' function.
We can put definition of
divides in a file: 'prime.hs'. After that we can start Haskell Interpreter and load that file in memory.
Prelude> :l prime
Then we can call it, to execute as follows:
*Main>divides 5 7
or
*Main>divides 5 30
When executed, it will be parsed, or converted into processor instructions and will return results
'immediately', without prior compilation needed. Because it's interpreted by Interpreter, instead of being compiled by Compiler.
3. Let's define & test 'ld' function.
'ld' stands for
'least divisor'.
For convenience we can define supporting function 'ldf' that finds least
divisor (pl: 'dzielnik') of a
dividend (pl: 'dzielna') n, starting from a given
threshold (pl: 'próg') k, with k ≤ n.
This means we are to find
least divisor of n, which is not less than k.
We have:
ld n = ldf 2 n
ldf k n | divides k n = k
| k^2 > n = n
| otherwise = ldf (k+1) n
(TODO: explain, nicely and precisely, what happens in above example, and how we can think about
guarded equations, such as with 'ldf' function.)
(TODO: finish Haskell Implementation for
Prime Number Test).
(Source: [1]).
