Wednesday, May 12, 2010

Finding number of divisors of large numbers

Problem 12 was taking a long time to run (too long to fit within the 1 minute execution benchmark), because I was checking every integer value less than n to determine whether it was a factor. However, when I changed the program to check only up to the square root of n, then assuming that factors come in pairs (unless the square root itself is an integer), then it ran much faster. Probably five seconds for the whole thing, down from not finishing in over an hour. I guess that since the final value was over 76 million, it was taking a long time to do the calculation for every triangle number up to that and then checking all the values up to 76 million. Also got a chance to review casting and thinking about doing calculations outside loops whenever possible, so that they don't have to be done every time inside the loop.

No comments:

Post a Comment