Самое маленькое количество, которое является равномерно делимым всеми числами от 1 до 20?

Наименьшее число, которое делится на два числа, это LCM из этих двух чисел. На самом деле, наименьшее число, делимое на множество N чисел x1...xN - это LCM этих чисел. Легко вычислить LCM двух чисел (см. статью в Википедии), и вы можете расширить его до N чисел, используя тот факт, что

LCM(x0,x1,x2) = LCM(x0,LCM(x1,x2))

Примечание: Остерегайтесь переполнений.

Код (на Python):

def gcd(a,b):
    return gcd(b,a%b) if b else a

def lcm(a,b):
    return a/gcd(a,b)*b

print reduce(lcm,range(2,21))

Коэффициент всех целых чисел от 1 до 20 в их простые факторизации. Например, коэффициент 18 как 18 = 3^2 * 2. Теперь для каждого простейшего числа p, которое появляется в простейшей факторизации некоторого целого в диапазоне от 1 до 20, находим максимальный экспоненту, который он имеет среди всех этих простейших факторизаций. Например, простое 3 будет иметь экспоненту 2, так как оно появляется в простейшей факторизации 18 как 3^2 и если оно появляется в любой простейшей факторизации с экспонентом 3 (т.е. 3^3), то это число должно быть не менее 3^3 = 27, которое оно выходит за пределы диапазона от 1 до 20. Теперь соберите все эти приметы с соответствующим показателем, и вы получите ответ.

Итак, в качестве примера, давайте найдем наименьшее число, равномерно делимое на все числа от 1 до 4.

2 = 2^1
3 = 3^1
4 = 2^2

Появившиеся праймы - это 2 и 3. Мы отмечаем, что максимальный показатель 2 равен 2, а максимальный показатель 3 равен 1. Таким образом, наименьшее число, которое равномерно делится на все числа от 1 до 4, составляет 2^2 * 3 = 12.

Вот относительно простая реализация.

#include <iostream>
#include <vector>

std::vector<int> GetPrimes(int);
std::vector<int> Factor(int, const std::vector<int> &);

int main() {
    int n;
    std::cout << "Enter an integer: ";
    std::cin >> n;
    std::vector<int> primes = GetPrimes(n);
    std::vector<int> exponents(primes.size(), 0);

    for(int i = 2; i <= n; i++) {
        std::vector<int> factors = Factor(i, primes);
        for(int i = 0; i < exponents.size(); i++) {
            if(factors[i] > exponents[i]) exponents[i] = factors[i];
        }
    }

    int p = 1;
    for(int i = 0; i < primes.size(); i++) {
            for(int j = 0; j < exponents[i]; j++) {
            p *= primes[i];
        }
    }

    std::cout << "Answer: " << p << std::endl;
}

std::vector<int> GetPrimes(int max) {
    bool *isPrime = new bool[max + 1];
    for(int i = 0; i <= max; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    int p = 2;
    while(p <= max) {
        if(isPrime[p]) {
            for(int j = 2; p * j <= max; j++) {
                isPrime[p * j] = false;
            }
        }
        p++;
    }

    std::vector<int> primes;

    for(int i = 0; i <= max; i++) {
        if(isPrime[i]) primes.push_back(i);
    }

    delete []isPrime;
    return primes;
}

std::vector<int> Factor(int n, const std::vector<int> &primes) {
    std::vector<int> exponents(primes.size(), 0);
    while(n > 1) {
        for(int i = 0; i < primes.size(); i++) {
        if(n % primes[i] == 0) { 
        exponents[i]++;
            n /= primes[i];
        break;
        }
            }
    }
    return exponents;
}

Выборочный вывод:

Enter an integer: 20
Answer: 232792560

See http://en.wikipedia.org/wiki/Greatest_common_divisor Учитывая два числа a и b, вы можете вычислить gcd(a, b), а наименьшее число, кратное обоим, это * b / gcd(a, b). Очевидная вещь, которая тогда должна быть сделана, состоит в том, чтобы держать своего рода запущенную сумму этого и добавлять в числа, о которых вы заботитесь один за другим: у вас есть ответ пока что A, и вы добавляете в следующее число X_i для рассмотрения, поставив

A' = A * X_i / (gcd(A, X_i))

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

Подсказка:

вместо увеличения NUM на 1 на каждом шаге вы можете увеличить его на 20 (будет работать быстрее). Конечно, могут быть и другие улучшения, я думаю об этом позже, если у меня будет время. Надеюсь, я немного помог тебе.

Это может помочь вам http://www.mathwarehouse.com/arithmetic/numbers/preime-number/preime-factorization.php?number=232792560

Главная факторизация 232 792 560

2 ^ 4 • 3 ^ 2 • 5 • 7 • 11 • 13 • 17 • 19

Оцененный номер наименее распространенные множественные числа с 1 по 20.

, потому что я ленивый, пусть ** представляют экспоненцию. Пусть Kapow (x, y) представляют целочисленную часть журнала к основанию x y. (Например, Капоу (2,8) = 3, Капоу (2,9) = 3, Капоу (3,9) = 2.

простые простые простые или равные 20 составляют 2, 3, 5, 7 , 11, 13 и 17. LCM - это,

, потому что SQRT (20) <5, мы знаем, что Kapow (I, 20) для I> = 5 - 1. При проверке, LCM

LCM = 2 Капоу (2,20) * 3 Капоу (3,20) * 5 * 7 * 11 * 13 * 17 * 19

Какой

LCM = 2 4 * 3 2 * 5 * 7 * 11 * 13 * 17 * 19

или

LCM = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19

Учитывая максимальное n, вы хотите вернуть наименьшее число, которое можно разделить на 1-20.

Давайте посмотрим на набор от 1 до 20. Во-первых, оно содержит число простых чисел, а именно:

2
3
5
7 
11
13
17
19

Таким образом, так как оно должно быть делимым на 19, вы можете проверить только кратные числа 19, так как 19 является простым числом. После этого проверяется, можно ли его разделить на меньшее число и т.д. Если число можно успешно разделить на все простые числа, то его можно разделить на числа с 1 по 20.

float primenumbers[] = { 19, 17, 13, 11, 7, 5, 3, 2; };

float num = 20;

while (1)
{
   bool dividable = true;
   for (int i = 0; i < 8; i++)
   {
      if (num % primenumbers[i] != 0)
      {
         dividable = false;
         break;
      }
   }

   if (dividable) { break; }
   num += 1;
}

std::cout << "The smallest number dividable by 1 through 20 is " << num << std::endl;