StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Since you asked, to make it faster a different algorithm should be used. Simple and straightforward is to find a prime factorization first, then construct the divisors from it somehow.</p> <p>Standard <a href="http://www.haskell.org/haskellwiki/Testing_primality#Primality_Test_and_Integer_Factorization" rel="nofollow noreferrer">prime factorization by trial division</a> is:</p> <pre class="lang-hs prettyprint-override"><code>factorize :: Integral a => a -> [a] factorize n = go n (2:[3,5..]) -- or: `go n primes` where go n ds@(d:t) | d*d > n = [n] | r == 0 = d : go q ds | otherwise = go n t where (q,r) = quotRem n d -- factorize 12348 ==> [2,2,3,3,7,7,7] </code></pre> <p>Equal prime factors can be grouped and counted:</p> <pre class="lang-hs prettyprint-override"><code>import Data.List (group) primePowers :: Integral a => a -> [(a, Int)] primePowers n = [(head x, length x) | x <- group $ factorize n] -- primePowers = map (head &&& length) . group . factorize -- primePowers 12348 ==> [(2,2),(3,2),(7,3)] </code></pre> <p>Divisors are usually constructed, though out of order, with:</p> <pre class="lang-hs prettyprint-override"><code>divisors :: Integral a => a -> [a] divisors n = map product $ sequence [take (k+1) $ iterate (p*) 1 | (p,k) <- primePowers n] </code></pre> <p>Hence, we have</p> <pre class="lang-hs prettyprint-override"><code>numDivisors :: Integral a => a -> Int numDivisors n = product [ k+1 | (_,k) <- primePowers n] </code></pre> <p>The <code>product</code> here comes from the <code>sequence</code> in the definition above it, because <code>sequence :: Monad m => [m a] -> m [a]</code> for list monad <code>m ~ []</code> constructs lists of all possible combinations of elements picked by one from each member list, <code>sequence_lists = foldr (\xs rs -> [x:r | x <- xs, r <- rs]) [[]]</code>, so that <code>length . sequence_lists === product . map length</code>, and or course <code>length . take n === n</code> for infinite argument lists. </p> <p>In-order generation is possible, too:</p> <pre class="lang-hs prettyprint-override"><code>ordDivisors :: Integral a => a -> [a] ordDivisors n = foldr (\(p,k)-> foldi merge [] . take (k+1) . iterate (map (p*))) [1] $ reverse $ primePowers n foldi :: (a -> a -> a) -> a -> [a] -> a foldi f z (x:xs) = f x (foldi f z (pairs xs)) where pairs (x:y:xs) = f x y:pairs xs pairs xs = xs foldi f z [] = z merge :: Ord a => [a] -> [a] -> [a] merge (x:xs) (y:ys) = case (compare y x) of LT -> y : merge (x:xs) ys _ -> x : merge xs (y:ys) merge xs [] = xs merge [] ys = ys {- ordDivisors 12348 ==> [1,2,3,4,6,7,9,12,14,18,21,28,36,42,49,63,84,98,126,147,196,252,294,343,441,588, 686,882,1029,1372,1764,2058,3087,4116,6174,12348] -} </code></pre> <p>This definition is productive, too, i.e. it starts producing the divisors right away, without noticeable delay:</p> <pre class="lang-hs prettyprint-override"><code>{- take 20 $ ordDivisors $ product $ concat $ replicate 5 $ take 11 primes ==> [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] (0.00 secs, 525068 bytes) numDivisors $ product $ concat $ replicate 5 $ take 11 primes ==> 362797056 -} </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload