CODEWITHSUNDEEP
haskell
HoRnsUp
HoRnsUp

Reputation: 53

Least common multiple without using gcd

With gcd its fairly easy but i do not understand how to tie in all the functions to make it happen without. 

kgv :: Int -> Int -> Int
kgv x y =  abs ((x `quot` (gcd x y)) * y)

I got this function to find the prime factors which works (prime_factors) and I am working on making a function that takes the maximum number from one list and checks if its on the other list (comp):

prime_factors :: Int -> [Int]
prime_factors 1 = []
prime_factors n
  | factors == []  = [n]
  | otherwise = factors ++ prime_factors (n `div` (head factors))
  where factors = take 1 $ filter (\x -> (n `mod` x) == 0) [2 .. n-1]


comp :: [Int]->Int
comp (ys)(x:xs)
 |maximum prime_factors xs elem prime_factors ys == x
 |otherwise tail x


kgv :: Int -> Int -> Int
kgv x y =  abs ((x `quot` (comp x y)) * y)

Upvotes: 1

Views: 698

Answers (4)

HoRnsUp
HoRnsUp

Reputation: 53

I figured it out myself mostly. Thanks for the ideas and pointers.

ggt n m   | n > m     = maximum [t | t <- [1 .. m], gt n m t]
    | otherwise = maximum [t | t <- [1 .. n], gt n m t]
gt n m c              = t n c  && t m c
t n c     | n >= c    = (mod n c == 0)
    | otherwise = False

kgv :: Int -> Int -> Int
kgv x y |x==0=0|y==0=0 |otherwise = abs ((x `quot` (ggt x y)) * y)

Upvotes: 0

dfeuer
dfeuer

Reputation: 48611

Here's an absurdly simple and obscenely inefficient solution:

lcm m n = head [x | x <- [1..], x `rem` m == 0, x `rem` n == 0]

Of course, this relies on two different notions of "least" coinciding under the circumstances, which they do. A fully naive solution doesn't seem possible.

Upvotes: 3

karakfa
karakfa

Reputation: 67507

perhaps another easy way is

import Data.List(intersect)
lcm m n = head $ intersect (series m n) (series n m)     
    where series a b = take a $ map (*b) [1..]

Upvotes: 3

Random Dev
Random Dev

Reputation: 52290

here is the (very) naive algorithm I was talking about:

kgv :: (Ord a, Num a) => a -> a -> a
kgv x y = find x y
  where find i j
          | i == j = i
          | i < j = find (i+x) j
          | i > j = find i (j+y)

it's basically what a school-child would do ;)

caution I ignored negative numbers and 0 - you'll probably have to handle those

Upvotes: 3

Related Questions