Sort 6 Discussions, By:
Please Login in order to post a 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
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.
yes if you know what you are doing - but functional programming is not basic number theory (not all programmers have a math background)
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).
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.
A Haskell IO template I use
countCommonDivisors :: Int -> Int -> Int
countCommonDivisors a b = -- give your solution over here
main = do
s <- getContents
let u = [map read (words s) | s <- (tail . lines) s]
putStrLn $ unlines $ map show [countCommonDivisors a b | [a, b] <- u]
Unfortunately, I haven't arrived at that simple algebraic formula. Therefore, I solved the problem counting the number of all possible common divisors algorithmically.
import Data.List ( group )
count' :: [Int] -> [Int]
count'  = 
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
Testcase 2 has the following input:
The output is:
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?
80 and 55 have 1 and 5 in common. Every case has at least the number 1 in common.
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
\x -> do
let mn = words x
putStrLn $ show (getCommonDivisors (head mn) (last mn))) (tail l)
No more comments