Project Euler #12 very long runtime

Question

Project Euler Problem 12 asks to find the value of the first triangular number to have over 500 divisors, where the \$n\$^th triangular number is \$\sum_{i=1}^{n} i\$.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be \$1 + 2 + 3 + 4 + 5 + 6 + 7 = 28\$. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

I have the following code written in C#. I never had the patience to wait for the program to finish but the code shows the right answer because I tried the example on their website. My code has a very long runtime and I don't know what to do to optimize it. I've waited for like 5-6 minutes on a AMD 4x cores 3.10 GHz and nothing...

static void Main(string[] args) {

        Stopwatch time = new Stopwatch();
        time.Start();

        int trianglenumber = 0;
        int divizori = 0;

            for (int i = 1; i < Int32.MaxValue; i++) {
                int tempnumber = 0;
                for (int j = 1; j < i; j++) {
                    tempnumber += j;
                }
                for (int k = 1; k < tempnumber+1; k++) {
                    if (tempnumber % k == 0) {
                        divizori++;
                    }
                }
                if (5 < divizori) {
                    trianglenumber = tempnumber;
                    break;
                }
                divizori = 0;
            }

            time.Stop();

            double timp = time.ElapsedMilliseconds ;

            Console.WriteLine(trianglenumber);
            Console.Write("Runtime: " + timp/1000+ " seconds");
            Console.ReadKey();


    }

Answer 1

You should change your algorithm. First note that triangle numbers can be written as: \$ T_n = \frac{n(n+1)}{2} \$ then notice that \$n\$ and \$n+1\$ cannot share a common divisor. So you can find all the divisors of \$T_n\$ just by finding the divisors of \$n\$ and \$n+1\$ (and removing a factor 2) and multiplying them together. This alone should greatly improve your algorithm turning it (the part inside the main loop) from \$O(n^2)\$ to \$O(n)\$.

Then you could make a table of prime number to quickly find the factorization of \$n\$ and \$n+1\$. Once you know the prime factors of \$n\$ you can find the number of all divisors of \$n\$. See, for example, here: http://www.marksmath.com/math/problems/count-div.html

addendum

First advice is actually enough. Here is the code (I don't know C#, hope it compiles):

static int count_divisors(int n) {
  int count = 0;
  for (int k=1;k<=n;++k) {
    // this loop can be reduced further by noticing that
    // apart from n itself there is no divisor with k*2>n
    if (n % k == 0) count++;
  }
  return count;
}

static void Main(string[] args) {
  int last_d = 0; // cache the computation for previous n
  for (int n=0;;++n) {
    int triangular = n*(n+1)/2; // only used for debugging and clarity
    int d; // number of divisors of (n+1) (or (n+1)/2 if (n+1) is even)
    if (n%2==0)
      d = count_divisors(n+1);
    else
      d = count_divisors((n+1)/2); // n+1 is even                               
    // # of divisors of n * (n+1)/2 is the product of divisors
    // since two consecutive numbers do not share any divisor (apart from 1)
    int total = d*last_d;
    if (total>500) {
      Console.WriteLine("found: " + triangular);
      break;
    }
    last_d = d; // cache the computation
  }
}