We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Functional Programming
  3. Ad Hoc
  4. Common Divisors
  5. Discussions

Common Divisors

Sort 6 Discussions, By:

votes

  • ahmedrazasaeed + 2 comments

    An efficient way to find all the factors for a number is to first find factors less than or equal to the root of the number.

    For example for 26 the root is 5.099. Using the above method we have to test just 5 numbers instead of 25. Only 100 tests in case of 10000.

    The factors greater than the root can be found by dividing the number by the factors less than or equal to the number.

    Finding the intersection of the factors of all numbers is trivial after that.

    • ahmedrazasaeed + 0 comments
      [deleted]
    • ecastilla95 + 0 comments

      With Scala:

      val set = (1 to sqrt(n).ceil.toInt).filter(n % _ == 0).toSet
set ++ set.map(n / _)

  • CKoenig + 1 comment

    IMO this is to much work/optimization for an easy problem - neither the most trivial (bruteforce the common divisors) nor the first order optimization (only bruteforce the divisors of the GCD) will run in time

    • blubberdiblub + 1 comment

      I don't know about the other languages, but it's very easy in Racket, as you can just compose 3 existing functions which do all the work.

      • CKoenig + 1 comment

        yes if you know what you are doing - but functional programming is not basic number theory (not all programmers have a math background)

        • blubberdiblub + 0 comments

          Indeed, at least partly. I don't really have a math background, either. Therefore a good library provided by the language can make the task easier in case you care to look and happen to be able to connect the strings (figuratively).

  • Elmex90s + 1 comment

    A Haskell IO template I use

    countCommonDivisors :: Int -> Int -> Int
countCommonDivisors a b = undefined -- give your solution over here

myProgram :: String -> String
myProgram t = unlines $ map show [countCommonDivisors a b | [a, b] <- u]
    where		
	u = [map read (words s) | s <- (tail . lines) t] 


main = do     
    s <- getContents    
    putStrLn $ myProgram s
    • hololeap + 1 comment

      I usually use some variation of this, and I find it to be cleaner (IMO)

      import Control.Monad

main = do
    t <- read <$> getLine
    replicateM_ t $ do
        [m,n] <- fmap read . words <$> getLine
        print $ countCommonDivisors m n
      • Elmex90s + 1 comment

        I updated my template. I think it is now very clean as I do as less as possible in the IO monad.

        • hololeap + 0 comments

          You might find the interact function from Prelude useful:

          interact :: (String -> String) :: IO ()

          Then you could do:

          main = interact myProgram

  • penkovsky + 0 comments

    Unfortunately, I haven't arrived at that simple algebraic formula. Therefore, I solved the problem counting the number of all possible common divisors algorithmically.

    Spoiler ahead!

    import Data.List ( group )

count' :: [Int] -> [Int]
count' [] = [0]
count' [x] = [x]
count' (x:xs) = [x] ++ count' xs ++ map (x*) (count' xs)

count :: [Int] -> Int
count = sum . count'

-- 1 stands for the trivial divisor (one)
numDivisors m l = 1 + count ns
  where ns = map length $ group $ factorize $ gcd m l

  • vamsikal2 + 1 comment

    Testcase 2 has the following input: 8 27 76 16 21 11 10 52 68 80 55 80 71 56 16 39 55 The output is: 1 1 1 3 2 1 4 1 which means for 80 55 the expected number of common factors is 2. 80 = 2^4 * 5 while 55 = 5 * 11, the number of common factors is 1, not 2. Can somebody look into this?

    • nswilson + 0 comments

      80 and 55 have 1 and 5 in common. Every case has at least the number 1 in common.

  • alexprut + 0 comments

    Beautiful but not efficien Haskell solution:

    getCommonDivisors m n = length [i | i <- [1..(gcd m n)], (mod m i) == 0, (mod n i) == 0]

main = do
    input <- getContents
    let l = lines input
    mapM_ (
        \x -> do
            let mn = words x
            putStrLn $ show (getCommonDivisors (head mn) (last mn))) (tail l)

No more comments