Is this Project Euler #5 solution more efficient than a known one?

Question

Here's my solution to Project Euler problem #5:

#include <stdio.h>
#include <stdint.h>

#define N 20

int main( int argc, char* argv[] )
{
   uint64_t r = 1;
   uint64_t i, j;

   for( i = 2; i <= N; ++i )
      if( (j = r%i) )
         r *= ( (i%j) ? i : (i/j) );

   printf( "\n%llu\n", r );

   return 0;
}

It is of O(n) efficiency. I've looked through a few pages of the official thread containing various solutions, but I didn't note any with an efficiency of O(n) or less. I wouldn't be surprised if I'm simply implementing some known solution, but if I am, I can't find it. Thoughts?

Answer 1

I did it with paper/pencil.

Find lcm(1, 2, ..., 20)(Least Common Multiple) of the numbers in the specified range. You could easily prove that you can reduce the above solution to:

lcm(11, 12, ..., 20)

Which is left as an exercise to the readre ;)

Answer 2

The problem is, your algorithm isn't completely correct. For example, for 27 it returns 722820898800, while 80313433200 is smaller and also valid (divisible by 2..27).

In your loop body, you seem to do first two steps of Euclid's algorithm to find greatest common divisor. While for small numbers two steps is enough, bigger numbers require more operations (that's why recursion is used).

So, your solution can be fixed like this ('gcd' stands for greatest common divisor)

for( i = 2; i <= N; ++i )
    r *= i / gcd(i, r);