Как найти нок числа в питоне

Давайте рассмотрим библиотеки math и numpy для решения математических задач.

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

Библиотека math

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

• Функции теории чисел и функции представления. Рассмотрим некоторые из них:

  • math.comb(n, k) — возвращает количество сочетаний из n элементов по k элементам без повторений и без учёта порядка. Определим, сколькими способами можно выбрать 3 объекта из множества в 12 объектов (порядок не важен):

    import math
    
    print(math.comb(12, 3))  # 220
    

  • math.factorial(x) — возвращает факториал целого неотрицательного числа x:

    print(math.factorial(5))  # 120
    

  • math.gcd(*integers) — возвращает наибольший общий делитель (НОД) для чисел-аргументов. Возможность определения НОДа для более чем двух чисел появилась в Python версии 3.9:

    print(math.gcd(120, 210, 360))  # 30
    

  • math.lcm(*integers) — возвращает наименьшее общее кратное (НОК) для чисел-аргументов. Функция появилась в Python версии 3.9:

    print(math.lcm(10, 20, 30, 40))  # 120
    

  • math.perm(n, k=None) — возвращает количество размещений из n элементов по k элементам без повторений и с учётом порядка. Если значение аргумента k не задано, то возвращается количество перестановок множества из n элементов:

    print(math.perm(4, 2))  # 12
    print(math.perm(4))  # 24
    

  • math.prod(iterable, start=1) — возвращает произведение элементов итерируемого объекта iterable. Если iterable пустой, то возвращается значение именованного аргумента start:

    print(math.prod(range(10, 21)))  # 6704425728000
    

• Степенные и логарифмические функции. Некоторые из функций:

  • math.exp(x) — возвращает значение экспоненциальной функции e^x:

    print(math.exp(3.5))  # 33.11545195869231
    

  • math.log(x, base) — возвращает значение логарифма от x по основанию base. Если значение аргумента base не задано, то вычисляется натуральный логарифм. Вычисление производится по формуле log(x) / log(base):

    print(math.log(10))  # 2.302585092994046
    print(math.log(10, 2))  # 3.3219280948873626
    

  • math.pow(x, y) — возвращает значение x в степени y. В отличие от операции **, происходит преобразование обоих аргументов в вещественные числа:

    print(math.pow(2, 10))  # 1024.0
    print(math.pow(4.5, 3.7))  # 261.1477575641718
    

• Тригонометрические функции. Доступны функции синус (sin(x)), косинус (cos(x)), тангенс (tan(x)), арксинус (asin(x)), арккосинус (acos(x)), арктангенс (atan(x)). Обратите внимание: угол задаётся и возвращается в радианах. Имеются особенные функции:

  • math.dist(p, q) — возвращает Евклидово расстояние между точками p и q, заданными как итерируемые объекты одной длины:

    print(math.dist((0, 0, 0), (1, 1, 1)))  # 1.7320508075688772
    

  • math.hypot(*coordinates) — возвращает длину многомерного вектора с координатами, заданными в позиционных аргументах coordinates, и началом в центре системы координат. Для двумерной системы координат функция возвращает длину гипотенузы прямоугольного треугольника по теореме Пифагора:

    print(math.hypot(1, 1, 1))  # 1.7320508075688772
    print(math.hypot(3, 4))  # 5.0
    

• Функции преобразования угла. Доступны функции:

  • math.degrees(x) — преобразует угол из радианов в градусы:

    print(round(math.sin(math.radians(30)), 1))  # 0.5
    

  • math.radians(x) — преобразует угол из градусов в радианы.

    print(round(math.degrees(math.asin(0.5)), 1))  # 30.0
    

• Гиперболические функции. Доступны функции acosh(x), asinh(x), atanh(x), cosh(x), sinh(x), tanh(x).

• Специальные функции. Среди специальных функций интерес представляет Гамма-функция. Она описывает гладкую непрерывную функцию f(x) = (x — 1)!, график которой проходит через точки, соответствующие значениям функции факториала для целых чисел. Другими словами, гамма-функция интерполирует значения факториала для вещественных чисел:

  print(math.gamma(3))  # 2.0
  print(math.gamma(3.5))  # 3.323350970447842
  print(math.gamma(4))  # 6.0
  

В библиотеке math можно воспользоваться значениями числа пи (math.pi) и экспоненты (math.e).

Библиотека numpy

Язык программирования Python удобен для быстрого создания программ с целью проверки какой-либо идеи. Однако зачастую его используют и в решении научных задач, а также при анализе больших данных и машинном обучении.
Возникает вопрос: каким образом может быстро обрабатывать много данных интерпретируемая, а не скомпилированная программа?
Оказывается, что в решении некоторых математических задач программы на Python могут быть такими же быстрыми, как и программы, созданные на компилируемых языках.

Существенную прибавку в скорости обеспечивает библиотека numpy (Numerical Python, читается как «нампАй»). Библиотека numpy частично написана на языках С и «Фортран», благодаря чему и работает быстро. Таким образом, numpy сочетает в себе вычислительную мощность языков С и «Фортран» и простоту синтаксиса Python.

Библиотека numpy является нестандартной библиотекой.

Нестандартные модули можно установить в Python несколькими способами. Мы рассмотрим самый простой — установку из репозитория PyPI (Python Package Index). Репозиторий — коллекция дополнительных библиотек для Python, хранящаяся на сервере. В настоящий момент количество библиотек в репозитории составляет более 400 тысяч.

Для установки библиотек из репозитория необходимо подключение к сети Интернет, а далее нужно выполнить команду в консоли (терминале):

pip install <название библиотеки>

Установим библиотеку numpy командой:

pip install numpy

После ввода команды начнётся загрузка установочного пакета и дополнительных библиотек, от которых зависит numpy. Затем начнётся процесс установки. Если установка пройдёт успешно, то вы увидите вывод в командной строке:

Successfully installed numpy

Для импорта numpy обычно используют следующий код:

import numpy as np

В программе мы сможем обращаться к numpy по новому имени — np. Это упростит чтение кода. Такой импорт широко используется сообществом программистов, поэтому стоит его придерживаться, чтобы ваш код был понятен каждому.

Библиотека numpy работает с объектами-массивами, которые способны хранить много значений и быть многомерными. При этом, в отличие от списков, массивы могут хранить только значения одного типа. За счёт этого массивы в numpy занимают меньше памяти и работают быстрее, чем списки.

Создать массив можно разными способами. Один из них — использовать функцию array() для преобразования списка в массив. Для доступа к элементам массива необходимо указать индекс элемента в квадратных скобках. Индексация начинается с нуля:

import numpy as np

a = np.array([1, 2, 3, 4])
b = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
print(f"a[0] = {a[0]}")
print(f"b[0] = {b[0]}")

Вывод программы:

a[0] = 1
b[0] = [1 2]

В нашем примере массив a имеет размерность, равную 1. Размерность массива b равна 2. В терминологии numpy массив a имеет одну ось (термин «axis» из документации) длиной четыре элемента, а массив b имеет две оси: первая имеет длину 4, а длина второй оси равна 2.

Массивы numpy являются объектами класса ndarray. Наиболее важными атрибутами класса ndarray являются:

• ndarray.ndim — размерность (количество осей) массива;
• ndarray.shape — кортеж, значения которого содержат количество элементов по каждой из осей массива;
• ndarray.size — общее количество элементов массива;
• ndarray.dtype — объект, описывающий тип данных элементов массива;
• ndarray.itemsize — размер памяти в байтах, занимаемый одним элементом массива.

import numpy as np

a = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
print(f"a.ndim = {a.ndim}, a.shape = {a.shape}, a.size = {a.size}, a.dtype = {a.dtype}")

Вывод программы:

a.ndim = 2, a.shape = (4, 2), a.size = 8, a.dtype = int32

Встроенные в numpy типы данных аналогичны типам данных в языке программирования С. Например, в предыдущем примере мы создали массив со значениями типа int32, то есть целые числа со знаком (отрицательные и положительные) и размером занимаемой памяти 32 бита. Из ограничения в размере памяти для типов данных в numpy следует то, что массивы каждого типа данных могут хранить значения из определённого диапазона. Например, для int32 этот числовой диапазон составляет от -2 147 483 648 до 2 147 483 647.

Покажем на примере, что произойдёт, если попытаться записать значение не из диапазона для типа данных. Для этого создадим массив типа uint8 — целые числа без знака размером 8 бит. Диапазон значений для этого типа от 0 до 255. Тип данных можно указать через именованный аргумент dtype при создании массива:

import numpy as np

a = np.array([1, 2, 3], dtype="uint8")
a[0] = 256
print(a)

Вывод программы:

[0 2 3]

Значение элемента не вышло за пределы диапазона, а было взято с его начала.

В numpy существуют и другие встроенные типы данных. С ними можно ознакомиться в документации.

При создании массива без указания его типа в аргументе dtype библиотека numpy попытается привести его к тому типу данных, который сможет хранить все значения исходной коллекции.

Рассмотрим пример:

import numpy as np

a = np.array([1, 2.5, 3])
print(a)
print(a.dtype)
b = np.array(['text', 1, 2.5])
print(b)
print(b.dtype)

Вывод программы:

[1.  2.5 3. ]
float64
['text' '1' '2.5']
<U32

В примере для массива a был выбран тип данных float64, так как исходный список содержит вещественное число. Для массива b был выбран тип данных <U32, который может хранить строки в кодировке Unicode длиной 32 символа. Такой тип данных был выбран, поскольку в исходной коллекции есть элемент-строка.

Для создания массива из нулей используется функция np.zeros(), которая принимает кортеж с количеством чисел, соответствующим количеству осей массива, а значения в кортеже — количество элементов по каждой из осей.

import numpy as np

a = np.zeros((4, 3))
print(a)
print()
a = np.zeros((4, 3), dtype="int32")
print(a)

Вывод программы:

[[0. 0. 0.]
 [0. 0. 0.]
 [0. 0. 0.]
 [0. 0. 0.]]

[[0 0 0]
 [0 0 0]
 [0 0 0]
 [0 0 0]]

Функция np.ones() создаёт массив аналогично функции np.zeros(), только из элементов-единиц.

import numpy as np

a = np.ones((4, 3))
print(a)

Вывод программы:

[[1. 1. 1.]
 [1. 1. 1.]
 [1. 1. 1.]
 [1. 1. 1.]]

Функция np.eye() создаёт единичную матрицу, то есть массив с единицами на главной диагонали и нулевыми остальными элементами:

import numpy as np

a = np.eye(5, 5, dtype="int8")
print(a)

Вывод программы:

[[1 0 0 0 0]
 [0 1 0 0 0]
 [0 0 1 0 0]
 [0 0 0 1 0]
 [0 0 0 0 1]]

Для создания массива, заполненного значениями из диапазона, используется функция np.arange(). Эта функция похожа на стандартную функцию range(), но возвращает массив и может создавать диапазон значений из вещественных чисел.

import numpy as np

a = np.arange(1, 10)
print(a)
print()
a = np.arange(1, 5, 0.4)
print(a)

Вывод программы:

[1 2 3 4 5 6 7 8 9]

[1.  1.4 1.8 2.2 2.6 3.  3.4 3.8 4.2 4.6]

Функция np.linspace() создаёт массив из заданного количества вещественных равномерно распределённых значений из указанного диапазона.

import numpy as np

a = np.linspace(1, 5, 10)  # задаётся начало, конец диапазона и количество значений
print(a)

Вывод программы:

[1.         1.44444444 1.88888889 2.33333333 2.77777778 3.22222222
 3.66666667 4.11111111 4.55555556 5.        ]

Для изменения размерности массива используется функция reshape(). Она принимает кортеж, значения которого задают новые размеры массива по осям. Функция reshape() возвращает новый массив. Обратите внимание: при изменении размерности количество элементов в массиве не должно измениться.

import numpy as np

a = np.zeros((4, 3), dtype="uint8")
print(a)
print()
a = a.reshape((2, 6))
print(a)

Вывод программы:

[[0 0 0]
 [0 0 0]
 [0 0 0]
 [0 0 0]]

[[0 0 0 0 0 0]
 [0 0 0 0 0 0]]

Метод resize() меняет размерность исходного массива:

import numpy as np

a = np.zeros((4, 3), dtype="uint8")
print(a)
print()
a.resize((2, 2, 3))
print(a)

Вывод программы:

[[0 0 0]
 [0 0 0]
 [0 0 0]
 [0 0 0]]

[[[0 0 0]
  [0 0 0]]

 [[0 0 0]
  [0 0 0]]]

Если при изменении размерности в функции reshape() указать значение -1 по одной или нескольким осям, то значения размерности рассчитаются автоматически:

import numpy as np

a = np.zeros((4, 3), dtype="uint8")
print(a)
print()
a = a.reshape((2, 3, -1))
print(a)

Вывод программы:

[[0 0 0]
 [0 0 0]
 [0 0 0]
 [0 0 0]]

[[[0 0]
  [0 0]
  [0 0]]

 [[0 0]
  [0 0]
  [0 0]]]

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

import numpy as np

a = np.array([9, 8, 7])
b = np.array([1, 2, 3])
print(a + b)
print(a - b)
print(a * b)
print(a / b)

Вывод программы:

[10 10 10]
[8 6 4]
[ 9 16 21]
[9.         4.         2.33333333]

Для умножения матриц используется операция @ или функция dot:

import numpy as np

a = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]])
b = np.array([[0, 0, 1],
              [0, 1, 0],
              [1, 0, 0]])
print(a @ b)

Вывод программы:

[[3 2 1]
 [6 5 4]
 [9 8 7]]

Матрицы можно транспонировать функцией transpose() и поворачивать функцией rot90(). При повороте можно указать направление поворота вторым аргументом:

import numpy as np

a = np.arange(1, 13).reshape(4, 3)
print(a)
print("Транспонирование")
print(a.transpose())
print("Поворот вправо")
print(np.rot90(a))
print("Поворот влево")
print(np.rot90(a, -1))

Вывод программы:

[[ 1  2  3]
 [ 4  5  6]
 [ 7  8  9]
 [10 11 12]]
Транспонирование
[[ 1  4  7 10]
 [ 2  5  8 11]
 [ 3  6  9 12]]
Поворот вправо
[[ 3  6  9 12]
 [ 2  5  8 11]
 [ 1  4  7 10]]
Поворот влево
[[10  7  4  1]
 [11  8  5  2]
 [12  9  6  3]]

Функции вычисления суммы элементов массива, поиска минимального и максимального элементов и многие другие по умолчанию работают для всех элементов массива, не учитывая размерность:

import numpy as np

a = np.array([[1, 2, 3],
             [4, 5, 6],
             [7, 8, 9]])
print(a.sum())
print(a.min())
print(a.max())

Вывод программы:

45
1
9

Дополнительно в указанных функциях можно указать номер оси (индексация с 0), на которой будет работать функция:

import numpy as np

a = np.array([[1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]])
print(a.sum(axis=0))  # сумма чисел в каждом столбце
print(a.sum(axis=1))  # сумма чисел в каждой строке
print(a.min(axis=0))  # минимум по столбцам
print(a.max(axis=1))  # максимум по строкам

Вывод программы:

[12 15 18]
[ 6 15 24]
[1 2 3]
[3 6 9]

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

import numpy as np

a = np.arange(1, 13).reshape(3, 4)
print(a)
print()
print(a[:2, 2:])
print()
print(a[:, ::2])

Вывод программы:

[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]

[[3 4]
 [7 8]]

[[ 1  3]
 [ 5  7]
 [ 9 11]]

В цикле for можно пройти по элементам первой оси массива:

import numpy as np

a = np.arange(1, 13).reshape(3, 4)
print(a)
for row in a:
    print(row)

Вывод программы:

[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]

[1 2 3 4]
[5 6 7 8]
[ 9 10 11 12]

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

import numpy as np

a = np.arange(1, 13).reshape(3, 4)
print(a)
print()
print("; ".join(str(el) for el in a.flat))

Вывод программы:

[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]

1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12

Покажем на примере различие в скорости работы массивов и списков. Посчитаем сумму квадратных корней первых 10⁷ чисел.

import numpy as np
from time import time

t = time()
print(f"Результат итератора: {sum(x ** 0.5 for x in range(10 ** 7))}.")
print(f"{time() - t} с.")
t = time()
print(f"Результат numpy: {np.sqrt(np.arange(10 ** 7)).sum()}.")
print(f"{time() - t} с.")

Вывод программы:

Результат итератора: 21081849486.439312.
1.7823209762573242 с.
Результат numpy: 21081849486.442448.
0.05197310447692871 с.

Библиотека numpy решила задачу в 30 раз быстрее, чем итератор.

За счёт скорости работы и удобной обработки массивов библиотека numpy используется для расчётов во многих других библиотеках. С одной из них мы поработаем в следующей главе.

Ещё по теме

Для более детального изучения библиотеки numpy рекомендуем почитать документацию.

В этой статье о Python мы рассмотрим, как получить наименьшее общее кратное (НОК) двух чисел. Для этого мы применим математическую формулу, опираясь также на наибольший общий делитель.

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

Давайте рассмотрим пример. Для чисел 20 и 6 есть кратные 60, 120 и другие.

Хотя существует несколько кратных чисел, нас интересует наименьшее из них, которым в данном случае является 60. Нет меньшего числа, которое было бы кратно обоим.

Формула

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

НОК(a, b) = (a * b) / НОД(a, b)

Здесь мы умножим a на b, а затем разделим результат на наибольший общий делитель (НОД) этих двух чисел.

Давайте перейдем к делу.

def min_common_divisor(a, b):
    return (a * b) / max_common_divisor(a, b)
Code language: JavaScript (javascript)

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

Собираем все вместе

Полный код вместе с функцией НОД выглядит следующим образом:

def max_common_divisor(a, b):
    temp = 0
    while b != 0:
        temp = b
        b = a % b
        a = temp
    return a
def min_common_divisor(a, b):
    return (a * b) / max_common_divisor(a, b)
a = 20
b = 6
nok = min_common_diviso
print(f"Наименьшее общее кратное {a} и {b} равно {nok}.")
Code language: PHP (php)