Представление числа в виде произведения простых множителей

Из различных разделов математики в спортивном программировании чаще всего встречаются элементы элементарной теории чисел. В этом разделе значительную роль имеет разложение числа на простые множители. Простыми называются такие числа, которые не имеют делителей кроме 1 и самого себя. Ряд простых чисел выглядит так:

Все остальные натуральные числа (кроме 1) называются составными, так как их можно представить в виде произведения нескольких простых чисел. Например:

Часто это записывается со степенями простых множителей:

Таким образом, любое число можно представить в виде произведения простых множителей следующим образом:

Согласно основной теореме арифметики, каждому числу однозначно соответствует такое представление, поэтому разложение числа на простые множители тесно связано с некоторыми его свойствами, и часто используется в решении задач.

Проверка числа на простоту

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

Реализация на C++:

1
2
3
4
5
6
7
8
9
bool is_prime(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }

    return true;
}

Сложность этого алгоритма . Существуют алгоритмы, позволяющие выполнять эту проверку быстрее (порядка ), но они исключительно редко применяются в спортивном программировании.

Факторизация

Факторизацией называется разложение числа на простые множители. Алгоритм факторизации основывается на тех же идеях, что и алгоритм проверки на простоту, приведённый выше. А именно: если у числа существует простой делитель, отличный от него самого, то он не превышает корня из числа. Для факторизации числа нужно перебрать все числа в промежутке , и попытаться разделить на каждое из них по очереди.

Реализация на C++ (Сложность: ):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> factorize(int x) {
    vector<int> factors;

    for (int i = 2; i <= sqrt(x); i++) {
        while (x % i == 0) {
            factors.push_back(i);
            x /= i;
        }
    }

    if (x != 1) {
        factors.push_back(x);
    }

    return factors;
}

Корректность этого алгоритма доказать также несложно. Заметим, что если при факторизации числа мы нашли делитель , то нам, по факту, осталось факторизовать число . Поэтому мы можем смело разделить число на и продолжить работу алгоритма. Мы можем не начинать проверку сначала, так как число гарантированно не имеет делителей меньше , иначе мы бы их уже нашли при факторизации .

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

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

Также можно реализовать алгоритм в виде поиска пар , где - множитель, - его степень:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
map<int, int> factorize(int x) {
    map<int, int> factors;

    for (int i = 2; i <= sqrt(x); i++) {
        while (x % i == 0) {
            factors[i]++;
            x /= i;
        }
    }

    if (x != 1) {
        factors[x]++;
    }

    return factors;
}

Поиск делителей

Поиск делителей числа и разложение его на множители - разные понятия, хотя термины в какой-то степени схожи. Под делителями числа подразумевают все числа, на которые оно делится. Пример для числа 20:

Множители
Делители

Алгоритм поиска делителей числа во многом похож на другие алгоритмы, приведённые выше. Мы рассматриваем делители парами: для каждого делителя мы учитываем соответствующий ему . Один из этих делителей гарантированно не превышает , поэтому, как и раньше, мы можем рассматривать только промежуток .

Реализация на C++ (Сложность: ):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> find_dividers(int x) {
    vector<int> dividers;

    for (int i = 1; i <= sqrt(x); i++) {
        if (x % i == 0) {
            dividers.push_back(i);

            //для корня из x не существует парного делителя
            if (i * i != x) {
                dividers.push_back(x / i);
            }
        }
    }

    return dividers;
}

Количество делителей

В качестве примера математических свойств представления числа в виде простых множителей приведём связь между характеристиками простых множителей числа и количеством его делителей.

Для этого давайте определим понятие делителя в контексте простых множителей. Запишем числа и в следующем виде:

Если какой-либо простой множитель не входит в разложение одного из чисел, то его степень в следующих рассуждениях принимается за 0.

Утверждение: частное двух чисел можно записать следующим образом:

Так как мы работаем с натуральными числами, это выражение имеет смысл тогда и только тогда, когда все степени простых множителей целые и неотрицательные. Отсюда можно выразить условие делимости двух чисел:

или

(Если вы не знакомы с подобной записью, обозначает “для всех ”)

Из этого условия можно легко вывести количество делитей. Ещё раз запишем в виде

Вспомним, что любому натуральному числу однозначно соответствует разложение на простые множители, то есть, набор степеней. Другими словами, изменение любой степени в наборе даст нам новое уникальное число.

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


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

Реализация на C++:

1
2
3
4
5
6
7
8
9
int dividers_count(map<int, int>& factors) {
    int result = 1;

    for (map<int, int>::iterator it = factors.begin(); it != factors.end(); it++) {
        result *= it->second + 1;
    }

    return result;
}

Реализация на C++11:

1
2
3
4
5
6
7
8
9
int dividers_count(map<int, int>& factors) {
    int result = 1;

    for (auto p: factors) {
        result *= p.second + 1;
    }

    return result;
}

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