Задача 25 ЕГЭ по информатике: разложение на множители, простые числа, количество делителей.

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

Разложение на множители.

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

Ускорить процедуру можно, если учесть тот факт, что если число n делится на число k, то оно делится и на n//k. Тогда можно проверить лишь числа от 2 до квадратного корня из n. Когда мы находим число k, на которое делится число n, то добавляем в список делителей два делителя: k и n//k. Один тонкий момент: если число n является точным квадратом числа k, то и k, и n//k - это одинаковые числа. Поэтому нужно ввести проверку и добавлять в список делителей n//k только в том случае, если это число не равно k. Тем самым мы избежим включения в массив делителей двух одинаковых чисел.

Приведем текст функции на Питоне, которая вычисляет все делители числа n, кроме единицы и самого числа n (так называемые нетривиальные делители) и возвращает массив, содержащий эти делители.

def divisors(n):
    d=[]
    k=2 # или 1, если требуются все делители
    while k*k <= n:
        if n%k == 0:
            d.append(k)
            k2 = n//k
            if k2 > k: d.append(k2)
        k += 1
    return d

Условие k*k <= n прекращает выполнение цикла поиска делителей, когда k станет больше, чем квадратный корень из n. Почему мы записали его так, а не в виде k<=sqrt(n)? На это есть две причины. 

Во-первых, операция умножения выполняется гораздо быстрее, чем извлечение корня. Во-вторых, функция извлечения корня возвращает вещественный результат. А операции над вещественными числами выполняются лишь приближенно, и квадратный корень из 4 при вычислениях может оказаться равным 2.0000000001, а может и 1.9999999999. Понятно, что это может сказаться на результате сравнения самым пагубным образом.

Данная функция находит только нетривиальные делители числа n, т.е. в список не попадает единица и само число n. Если требуются все делители, то строку k=2 в начале фунации следует заменить на k=1.

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

[2, 30, 3, 20, 4, 15, 5, 12, 6, 10]

Если требуется упорядоченность, то нужно отсортировать полученный массив.

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

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

Но можно написать для этой цели и отдельную функцию. Приведем её текст:

 

def isprime(n):
    k=2
    while k*k <= n:
        if n%k == 0: return False
        k += 1
    return True 

 

Функция возвращает True, если число n - простое.

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

Существуют и более быстрые алгоритмы для решения данных задач, но они достаточно сложны, и на ЕГЭ их не имеет смысла применять.

 

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

Вернемся к функции поиска делителей. Она находит делители парами (k и n//k). Единственное исключение - случай, когда наше число n является точным квадратом некоторого целого числа.

Отсюда следует очень важный факт:

Количество делителей числа n>1 нечетно тогда и только тогда, когда n - квадрат некоторого числа.

Рассмотрим вопрос о количестве делителей более подробно.

Любое натуральное число можно единственным образом представить в виде

p₁^m₁p₂^m₂...p_n^m_n,

где p_i - простые числа, а m_i - натуральные. (Это утверждение называется основной теоремой арифметики.)

Делителем данного числа будет являться любое число вида

p₁^k₁p₂^k₂...p_n^k_n,

где 0<=k_i<=m_i

Очевидно, что каждое k_i может принимать m_i+1 различных значений (0, 1, ...,  m_i). А количество всех делителей (включая 1 и само число) есть

(m₁+1)(m₂+1)...(m_n+1)

Пример: число 12 можно представить в виде 2²*3¹. Следовательно, у числа 12 должно быть (2+1)(1+1)=6 делителей. В самом деле, делители числа 12 - это 1, 2, 3, 4, 6 и 12.

Отсюда, в частности, следует, что если количество всех делителей некоторого числа n - простое число m, то n должно иметь вид p^m-1 (где p - простое число).

Это помогает решать задачи, в которых надо найти числа, имеющие, например, ровно 5 делителей. Так как 5 - простое число, то все такие числа должны иметь вид p⁴, где p - простое число. Пример такого числа - 81, т.е. 3⁴: его делители - 1, 3, 9, 27 и 81.

(c) Ю.Д.Красильников, 2021-2024 г.