Haskell beginner - recursive recursion

Question

Just starting with Haskell, and I put together this ugly part to figure out the numbers on the list, dividing the number and all the numbers less than it.

divis :: (Integral a) => a -> [a] -> [a] divis _ [] = [] divis n (x:xs) | x `mod` n == 0 && n == 2 = x : divis n xs | x `mod` n == 0 = divis (n-1) [x] ++ divis n xs | otherwise = divis n xs 

and I can call it like ...

 head (divis 10 [1..]) 

to get the first number in the list, in this case 2520. However, it seems that this is not effective enough for an effective solution using a larger number, for example 20.

How can I fix this raskell from haskell?

Answer 1

This can be significantly improved using another algorithm: the smallest number that can be divided into a set of numbers (in this case, the set [1..10]) is the smallest common multiple of these numbers.

Haskell even has a built-in function of least common function ( lcm ), which you can use:

 Prelude> foldl lcm 1 [1..10] 2520 

If you prefer not to use the built-in lcm function (as it’s almost a hoax :)), you can do this using the Euclidean algorithm to calculate the GCD, and then using:

 lcm ab = a * b `div` gcd ab 

If you need to find all the numbers in this list that are divisible by [1..n], you can use the fact that any such number will also be divisible by the least common multiple [1..n]:

 divis n xs = filter (\x -> x `mod` mult == 0) xs where mult = foldl lcm 1 [1..n]