Найти наименьшее общее кратное нескольких чисел

Question

Цель этой программы - найти наименьшее число, которое можно разделить на числа от 1 до 20 без остатков. Код работает, но это занимает 33 секунды. Могу ли я улучшить его, чтобы он был быстрее? Как?

#include <stdio.h>

int main(){
  int number = 19, i, k;

  label:
  number++;
  k = 0;
  for (i = 1; i <= 20; i++){
    if (number%i == 0){
      k++;
    }
  }

  if (k != 20){
    goto label;
  }

  printf("%d\n", number);
  return 0;
}

Answer 1

#include <stdio.h>


/*  GCD returns the greatest common divisor of a and b (which must be non-zero).

    This algorithm comes from Euclid, Elements, circa 300 BCE, book (chapter)
    VII, propositions 1 and 2.
*/
static unsigned GCD(unsigned a, unsigned b)
{
    while (0 < b)
    {
        unsigned c = a % b;
        a = b;
        b = c;
    }

    return a;
}


int main(void)
{
    static const unsigned Limit = 20;

    unsigned LCM = 1;

    /*  Update LCM to the least common multiple of the LCM so far and the next
        i.  The least common multiple is obtained by multiplying the numbers
        and removing the duplicated common factors by dividing by the GCD.
    */
    for (unsigned i = 1; i <= Limit; ++i)
        LCM *= i / GCD(LCM, i);

    printf("The least common multiple of numbers from 1 to %u is %u.\n",
        Limit, LCM);
}

Answer 2

Вам нужно умножить все наименьшие общие множители вместе, но опустить числа, которые можно умножить, чтобы получить любое из остальных.Это означает умножение на все простые числа, меньшие N, с каждым простым числом, возведенным в наивысшую степень <= N. </p>

const unsigned primes[] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
};

unsigned long long answer(unsigned n){ //for your example n=20
    if (n>46) return 0;  //will overflow 64 bit unsigned long long
    unsigned long long tmp, ret = 1;
    for (unsigned i = 0; primes[i]<=n;++i){ //each prime less than n
        tmp = primes[i];
        while ((tmp*primes[i])<=n) //highest power less than n
            tmp *= primes[i];
        ret *= tmp;
    }
    return ret;
}

использование: printf("%llu", answer(20));

Если моя математика / код верныэто должно быть быстро и охватывать числа до 46. Если ваш компилятор поддерживает беззнаковое __int128, его можно изменить так, чтобы оно доходило до 88.

Объяснение: Версия TLDR: все числа либо простые, либо могут быть получены путем умножения простых чисел..

Чтобы получить наименьшее общее кратное из набора чисел, вы разбиваете каждое число на его простые множители и умножаете наибольшее число каждого простого числа.

Простые числа меньше 20:2,3,5,7,11,13,17,19

Не простые числа до 20 лет: 4 = 2 * 2 6 = 2 * 3 8 = 2 * 2 * 2 9 = 3 * 3 10 =2 * 5 12 = 2 * 2 * 3 14 = 2 * 2 * 7 15 = 3 * 5 16 = 2 * 2 * 2 * 2 18 = 2 * 3 * 3 20 = 2 * 2 * 5

Из этого мы видим, что максимальное число 2 равно 4, а максимальное число 3 равно 2.

2 до четвертого <= 20 3 в квадрате <= 20 Все способности> 1 из остальных простых чисел большечем 20.

Поэтому вы получаете:

2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19

То, что вы бы увидели, если бы смотрелипеременная tmp в отладчике.

Другая причина, по которой это происходит быстрее, заключается в том, что он избегает модуля и деления (это дорого для многих систем)

Answer 3

Изменение

int number = 19 ;

на

int number = 0 ;

, затем:

number++;

на

number += 20 ;

- очевидное улучшение, которое будетокажут значительное влияние, даже если это все еще довольно наивный подход грубой силы.

На сайте onlinegdb.com ваш алгоритм работал за 102 секунды, тогда как это изменение выполняется менее чем за одну секунду и дает тот же ответ.

Исходное произведение значения простых чисел, предложенное в комментарии, обеспечит дальнейшее улучшение.

Answer 4

Вот способ сделать это без определения простых чисел или делений (за исключением одного sqrt), используя Сито Эратосфена (около 200 г. до н.э.).

Я отмечаю композиты с 1и простые числа ^ x с -1.Затем я просто перебираю массив чисел от sqrt (n) до n и извлекаю оставшиеся простые и максимальные простые числа.

#include <stdio.h>
#include <math.h>

#define n 20

int main()
{
    int prime [100]={0};
    int rootN = sqrt(n);
    unsigned long long inc,oldInc;
    int i;
    for (i=2; i<rootN; i++)
    {
        if (prime[i] == 1) continue;
        //Classic Sieve
        inc = i*i;
        while (inc < n)
        {
         prime[inc] = 1;
         inc += i;
        }
        //Max power of prime
        oldInc = i;
        inc = i * i;
        while (inc < n)
        {
         prime[inc] = 1;
         oldInc=inc;
         inc *= i;
        }
        prime[oldInc] = -1;
        prime[i] = 1;

    }
    inc = 1;
    for(i=rootN; i<n; i++)
    {
        if (prime[i] == 0 || prime[i] == -1)
        {
            inc = inc * i;
        }
    }

    printf("%llu",inc);

    return 0;
}