Sort 6 Discussions, By:
Please Login in order to post a comment
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.
val set = (1 to sqrt(n).ceil.toInt).filter(n % _ == 0).toSet
set ++ set.map(n / _)
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).
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]
u = [map read (words s) | s <- (tail . lines) t]
main = do
s <- getContents
putStrLn $ myProgram s
I usually use some variation of this, and I find it to be cleaner (IMO)
main = do
t <- read <$> getLine
replicateM_ t $ do
[m,n] <- fmap read . words <$> getLine
print $ countCommonDivisors m n
I updated my template. I think it is now very clean as I do as less as possible in the IO monad.
You might find the interact function from Prelude useful:
interact :: (String -> String) :: IO ()
Then you could do:
main = interact myProgram
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