Является ли это решение Project Euler # 5 более эффективным, чем известное?

Question

Вот мое решение Проектной проблемы Эйлера # 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).

В теле вашего цикла вы, кажется, делаете первые два шага Алгоритм Евклида чтобы найти наибольший общий делитель.В то время как для небольших чисел достаточно двух шагов, для больших чисел требуется больше операций (поэтому используется рекурсия).

Итак, ваше решение можно исправить следующим образом ('gcd' обозначает наибольший общий делитель)

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

Answer 2

Я сделал это с бумагой / карандашом.

Найдите lcm(1, 2, ..., 20) (наименьшее общее кратное) чисел в указанном диапазоне.Вы можете легко доказать, что вы можете уменьшить приведенное выше решение до:

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

, которое оставлено в качестве упражнения для чтения;)

Answer 3

Мой первоначальный подход был очень похож на ваш и потребовалось целое время, чтобы получить результаты. Этот сделал это за несколько секунд Я умножил все простые числа в диапазоне от 1 до 20 (2, 3, 5, 7, 11, 13, 17, 19) Идея состояла в том, что у простых чисел нет GCD, и наименьшее допустимое число должно быть их продукта.

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

Излишне говорить, что это далеко не идеальный код, но он выполнил свою работу.