Project Euler#5解决方案比已知解决方案更有效吗？

Question

这是我对Project Euler问题#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;
}

它具有O(n)效率.我查看了包含各种解决方案的官方帖子的几页,但我没有注意到O(n)或更低的效率.如果我只是简单地实现一些已知的解决方案,我不会感到惊讶,但如果我是,我找不到它.思考？

Answer 1

问题是,你的算法并不完全正确.例如,对于27,它返回722820898800,而80313433200更小并且也有效(可被2..27整除).

在你的循环体中,你似乎做了Euclid算法的前两步来找到最大的公约数.虽然对于较小的数字,两个步骤就足够了,较大的数字需要更多的操作(这就是使用递归的原因).

所以,你的解决方案可以像这样修复('gcd'代表最大公约数)

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