# understanding the Haskell implementation of the least divisor function

Submitted by metaperl on Sat, 04/01/2006 - 5:55pm.

Ok, first LD(n) is the least divisor of n. It is a number, p, such
that p*a = n and a > p and p > 1.

So now to express LD(n) as a Haskell function:

``` ld n = ldf 2 n ```

``` Where ldf 2 n means the least divisor of n that is >= 2. Hopefully it is understood that the Haskell expression of ld(n) is equivalent to our initial mathematical definition. Now, something else that is asserted and then proved: n > 1 and n not prime IMPLIES (LD(n))^2 less than or equal to n So then the following definition of ldf k n is offered ld n = ldf 2 n ldf k n | divides n k = k | k^2 > n = n | otherwise = ldf (k+1) n But I do not understand why the second guard is true. Clearly it has to do with "n > 1 and n not prime IMPLIES (LD(n))^2 <= n" but I do not see how they relate. ```
``` metaperl's blog Login to post comments ```
``` Cale helped me out greatly Submitted by metaperl on Sat, 04/01/2006 - 11:13pm. Cale helped me out greatly with this problem fact: If n doesn't have a factor less than sqrt(n), then it must be prime Suppose that n = a*b, but n doesn't have a proper factor less than or equal to sqrt(n) so a > sqrt(n) and b > sqrt(n) and so a*b > sqrt(n)^2 and so a*b > n which is a contradiction Login to post comments Comment viewing options Flat list - collapsedFlat list - expandedThreaded list - collapsedThreaded list - expanded Date - newest firstDate - oldest first 10 comments per page30 comments per page50 comments per page70 comments per page90 comments per page150 comments per page200 comments per page250 comments per page300 comments per page Select your preferred way to display the comments and click "Save settings" to activate your changes. ```