Optimizing code that needs to run through a lot of different numbers for Project Euler I have been working on Project Euler problem number 12. I have code that will get me the right answer, however it takes too long. I know the code works because I have tested it multiple times with numbers that are smaller and take much less time to iterate through. I first wrote essentially the same thing in python, but I know C is faster so I gave it a shot in C, but my solution is just not efficient. Here is the code (in C):

#include &lt;stdio.h&gt;

int main(void) {
  int num = 0;
  int i;
  int j;
  int divisors = 0;
  for (i=1; i&lt;10000; i++){
    num += i;

    for (j=1; j&lt;=num; j++) {
      if (num % j == 0) {
        divisors += 1;
      }
    }

    if (divisors &gt; 500) {
      printf("Num is %d\n", num);
      printf("Divs are %d\n", divisors);
    }

    divisors = 0;

  }
}


Project Euler problems are supposed to be solved in under a minute of run-time anyways, so this isn't a great solution even if I let it run until I got an answer. 

Any suggestions on ways to do this faster would be much appreciated!
Iterating [1...num] is too slow
Only [1...sqrt(num)] needed 

Instead of 

for (j=1; j&lt;=num; j++) {
  if (num % j == 0) {
    divisors += 1;
  }
}


Go to the root of num (when j*j &lt;= num) and get 2 or 1 divisors.

for (j=1; j*j &lt;= num; j++) {
  if (num % j == 0) {
    divisors += 1;
    if (j*j &lt; num) divisors += 1;
  }
}


Re-formulate to avoid j*j overflow

for (j=1; j &lt; num/j; j++) {
  if (num % j == 0) {
    divisors += 2;
  }
}
if (j == num/j) {
  divisors += 1;
}


Note: Many compilers with recognize the nearby num/j and num % j and perform the operation for the time cost one of one.

Example

Consider num == 36.  Original code tries 36 numbers with the starred ones having an exact division.

1*,2*,3*,4*,5,6*,7,8,9*,10,11,12*,13,14,15,16,17,18*,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36*.

Notice that when num%j == 0, both j and num/j are divisors.  Except when j == num/j, that discovers two unique divisors at once.  Code only needs to  iterate to 6.

j=1, divisors: 1 &amp; 36
j=2, divisors: 2 &amp; 18
j=3, divisors: 3 &amp; 12
j=4, divisors: 4 &amp; 9
j=5, divisors: none
j=6, divisor: 6  

6 iterations faster than 36.

With a num = 1,000,000, new code will iterate to 1000 rather than 1,000,000 - a thousand times faster.



Detail on overflow possibility.

Consider num is at or near INT_MAX:

With for (j=1; j&lt;=INT_MAX; j++) {, j will attempt to increment beyond INT_MAX resulting in undefined behavior.  

With for (j=1; j*j &lt; near_INT_MAX; j++) {, Unless near_INT_MAX is a perfect square, j*j will overflow.  Again undefined behavior.

With for (j=1; j &lt; num/j; j++) {, j never overflow for all num.

====

There are many more advance techniques for faster code.