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

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

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

#define N 20
开发者_如何学C
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?

---

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);

---

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 ;)

---

My initial approach was very similar to yours and it took forever to produce the results. This one did it in a few seconds I multiplied all the primes in the range of 1 to 20 (2, 3, 5, 7, 11, 13, 17, 19) The idea was that primes have no GCD and the smallest eligible number would have to be of their product.

acnum=0.0
testnum=9699690
divisor=20.0
while acnum==0.0:    

    if testnum%divisor==0.0:
        divisor-=1.0

        print testnum, divisor
    else:
        testnum+=9699690
        divisor=20.0


    if divisor==1.0:
        acnum=testnum

Needless to say it's far from perfect code, but it got the job done.