# Common Divisors

# Common Divisors

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 timeblubberdiblub + 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

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

Sort 6 Discussions, By:

Please Login in order to post a comment