Haskell function takes a long time to process
I am asking question 12 of the euler project where should I find the first number of a triangle with 501 divisors. So I hacked it up with Haskell:
divS n = [ x | x <- [1..(n)], n `rem` x == 0 ]
tri n = (n* (n+1)) `div` 2
divL n = length (divS (tri n))
answer = [ x | x <- [100..] , 501 == (divL x)]
The first function finds the divisors of a number.
The second function calculates the nth triangle number
The third function finds the length of the list that is the divisor of the triangular number
The 4th function should return the value of the number of triangles with 501 divisors.
But for now, it runs for a while without returning a result. Is the answer very big or do I need some serious optimization to make this work in realistic time?
source to share
You need to use the properties of the divisor function: http://en.wikipedia.org/wiki/Divisor_function
Note that n and n + 1 are always relatively prime, so you can get d (n * (n + 1) / 2) by multiplying the previously calculated values.
source to share
It is probably faster to just transfer the number and then use factorization to find the divisors than using trial division with all numbers <= sqrt (n).
The Sieve of Eratosthenes is a classic way of finding primes, which can be slightly modified to find the number of divisors of each natural number. Instead of just labeling each non-simple as “not simple,” you could list all the prime numbers that divide every number. You can then use those primes to calculate the full set of divisors, or just the number of them, since that's all you need.
Another option would be to note not only the multiplicity of prime numbers, but also the multiplicity of all natural numbers. Then you can simply use a counter to keep track of the number of divisors for each number.
You can also check out The Genuine Sieve of Eratosthenes which explains why the trial division is much slower than the real sieve.
Finally, you should take a close look at the various types of arrays in Haskell. I think it might be easier to use the ST monad to implement the sieve, but the correct complexity could be achieved using accumArray if you can make sure your update function is strict. I have never been able to get this to work, so here you are.
source to share
If you used C instead of Haskell, your function will still take a long time.
To make it faster, you will need to improve the algorithm using suggestions from the above answers. I suggest changing the title and description of the question accordingly. After that I will delete this comment.
If you want I can screw up the problem by sharing my solution.
Now I will give you the top level code:
main =
print .
head . filter ((> 500) . length . divisors) .
map (figureNum 3) $ [1..]
Algorithmic improvement lies in function divisors
. You can improve it using rawicki's suggestion, but it already takes less than 100ms.
source to share