Is Project Euler Solution # 5 More Effective Than Known?

Question

Here is my solution. Problem with Euler project # 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;
}

This is the efficiency of O (n). I looked through several pages of the official topic containing various solutions, but I did not notice anything with an efficiency of O (n) or less. I would not be surprised if I just implement some well-known solution, but if I find it, I can’t find it. Thoughts?

Answer 1

The problem is that your algorithm is not entirely correct. For example, for 27 it returns 722820898800, and 80313433200 is smaller and also valid (divided by 2..27).

, , , . , ( ).

, ( "gcd" )

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

Answer 2

/.

lcm(1, 2, ..., 20) ( ) . , :

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

readre;)

Answer 3

My initial approach was very similar to yours, and it took forever to produce results. This did it in a few seconds. I multiplied all the primes in the range from 1 to 20 (2, 3, 5, 7, 11, 13, 17, 19) The idea was that the primes did not have a GCD, and the smallest number, eligible to participate must be in 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

Of course, this is far from complete code, but it did its job.