StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You needn't test <em>all</em> the elements of reversed second half. You know that if the square root is present, it is the head element there:</p> <pre><code> secondHalf = let (r:ds) = [n `div` d | d <- reverse firstHalf] in [r | n `div` r /= r] ++ ds </code></pre> <p>This assumes <code>n</code> is positive. </p> <p>A simpler way to handle the sqrt of a number differently is to handle it <em>separately</em>:</p> <pre class="lang-hs prettyprint-override"><code>divs n = let r = floor $ sqrt $ fromIntegral n (a,b) = unzip $ (1,n) : [(d, q) | d<-[2..r-1], let (q,r)=quotRem n d, r==0] in if r*r==n then a ++ r : reverse b else a ++ reverse b </code></pre> <p>That way we get the second half for free, as a part of producing the first half. </p> <p>But this could hardly be a bottleneck in your application because the algorithm itself is inefficient. It is usually much faster to <a href="https://stackoverflow.com/a/12052561/849891"><em>generate</em> the divisors from a number's prime factorization</a>. Prime factorization by trial division can be much quicker because we <em>divide out</em> each divisor as it is found, reducing the number being factorized and thus the amount of divisors that are tried (up to the <em>reduced</em> number's square root). For example, <code>12348 = 2*2*3*3*7*7*7</code> and no factor above <code>7</code> is tried in the process of factorization, whereas in <code>divs 12348</code> the number 12348 is divided by all numbers from <code>2</code> to <code>110</code>:</p> <pre class="lang-hs prettyprint-override"><code>factorize n = go n (2:[3,5..]) -- or: (go n primes) where where -- primes = 2 : go n ds@(d:t) -- filter (null.tail.factorize) [3,5..] | d*d > n = [n] | r == 0 = d : go q ds | otherwise = go n t where (q,r) = quotRem n d </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