Least divisor function
Function
| definiendum | ld:N+→{1}∪Prime number |
| definiendum | ld(n):=min(divisors(n)) |
Code
Haskell
divides :: Integral a => a -> a -> Bool divides d n = rem n d == 0
ld :: Integral a => a -> a ld n = ldf 2 n ldf :: Integral a => a -> a -> a ldf k n | divides k n = k | k^2 > n = n | otherwise = ldf (k+1) n
using Set of divisors function:
divides :: Integral a => a -> a -> Bool divides d n = rem n d == 0
Theorems
If n isn't a prime, then n divided by the least divisor is some number bigger than ld(n) and hence
| ld(n)2≤n |
|---|
Subset of
Requirements
Code reference
