Kraskevich's solution has one problem which is get the prime factors in set of 2,3,4,... In fact , we can get the primes in the set of 2,3,5,7,9...(2 and odd numbers), the bellow code avoids unnecessary operations on even numbers(greater than 2).
factors' :: Integral t => t -> [t]
| n < 0 = factors' (-n)
| n > 0 = if 1 == n
else let fac = mfac n 2 in fac : factors' (n `div` fac)
where mfac m x
| rem m x == 0 = x
| x * x > m = m -- if this line code can be matched, this is to say m can not be divided by 2,3,5,7,...n, n is the largest odd number less than sqrt(m). In other words, it is consistent with the definition of prime numbers.
| otherwise = mfac m (if odd x then x + 2 else x + 1) -- get factor in (2,3,5,7,9...)
In this problem, we should pay attention to
- give a number n, x bellow to the set of 2,3,4,...,n-1(in above code, we use its subset(2 and even number)). if n is the smallest number that can be divisible by x，then n is always a prime number.
- give a number n, we can define
n = p1 * p2 * p3 *...* pi * pj * ... pi is prime, pi <= pj so we can get
n/p1 = p2 * p3 * ...pi * pj..., what is p1? p1 is the number which gets in