1. Каноническое разложение натурального числа. 3
 Скачать 0.66 Mb.
|
Наибольший общий делитель.Наибольший общий делитель (GCD как аббревиатура в OEIS, но не в математических формулах; обычно gcd в литературе; иногда известный как высший общий множитель, HCF или hcf) двух или более целых чисел является наибольшим положительным целым числом, которое является общим делителем всех этих чисел, т.е. которое делит (дает целочисленное частное с 0 в качестве остатка) все эти числа. Например, gcd (144, 2988, 37116) = 36, так как 36 равномерно делит 144, 2988 и 37116, и для этих чисел нет большего общего делителя. Когда , числа называются копростыми или относительно простыми, такими как, например, gcd (128, 11025) = 1. Обратите внимание, что gcd (1, 1) = 1, что означает, что 1 является сопростым с самим собой, т.е. он не разделяет с собой простых множителей, так как 1 является пустым произведением.
. В частности, gcd (0, 0) = 0; по существу 0 выступает в качестве верхнего элемента (⊤ или ∞) в этом и других контекстах.  Алгоритм Евклида.Алгоритм Евклида — один из наиболее ранних численных алгоритмов в истории. Название было дано в честь греческого математика Евклида, который впервые дал ему описание в книгах «Начала». Изначально назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль. Сегодня чаще используется взятие остатка от деления вместо вычитания, но суть метода сохранилась. Суть алгоритма заключается в построении ряда следующего вида (при условии, что a больше b): a, b, x1, x2, x3, … xn. В нем каждое последующее число — это остаток от деления двух предыдущих, ряд заканчивается, когда остаток от деления становится равным 0 — при условии использования деления. В нем каждое последующее число является результатом вычитания двух предыдущих, ряд заканчивается, когда частное становится равным 0 — при условии использования вычитания. Решето Эратосфена.Решето Эратосфена — алгоритм нахождения всех простых чисел в сегменте [1; н] использование O(nloglogn) операционный. Алгоритм очень прост: в начале записываем все числа между 2 и n. Мы помечаем все собственные кратные 2 (так как 2 — наименьшее простое число) как составные. Правильное кратное числу x, — число, превышающее x и делится на x. Затем мы находим следующее число, которое не было помечено как составное, в данном случае это 3. Это означает, что 3 является простым, и мы помечаем все правильные кратные 3 как составные. Следующим немаркированным числом является 5, которое является следующим простым числом, и мы отмечаем все соответствующие кратные ему. И мы продолжаем эту процедуру до тех пор, пока не обработаем все числа в строке. Идея заключается в следующем: число является простым, если ни одно из меньших простых чисел не делит его. Поскольку мы перебираем простые числа по порядку, мы уже пометили все числа, которые делятся по крайней мере на одно из простых чисел, как делимые. Следовательно, если мы достигаем ячейки, и она не отмечена, то она не делится на какое-либо меньшее простое число и, следовательно, должна быть простой. Векторное пространство со скалярным умножением.бстрактное вещественное векторное пространство представляет собой коммутативную группу с одной дополнительной операцией: ее элементы могут быть умножены на вещественные числа (скаляры). Это ни в коем случае не групповая операция (за исключением случая, когда мы рассматриваем множество R вещественных чисел как вещественное векторное пространство), потому что в групповых операциях оба операнда должны исходить из одного и того же множества. Умножение на скаляр требуется для удовлетворения трех дополнительных законов: для u, v∈ и векторов a и b, (дистрибутивность): (u + v)a = ua + va (ассоциативность): u(va) = (uv)a (дистрибутивность): u(a + b) = ua + ub Это варианты дистрибутивных и ассоциативных законов. Как, например, для n-кортежных пространств умножение на скалярный определяется покомпонентно:
С этим определением и сложением, определенными также компонентно, множество 3-кортежей становится векторным пространством. Важно понимать, что n-кортеж рассматривается как вектор только тогда, когда он считается элементом множества, где определены две операции (сложение и умножение скаляром). Таким образом, векторы и векторные пространства рождаются одновременно. ля некоторых векторных пространств можно определить другое умножение - скалярное (или внутреннее, или точечное) произведение. Скалярное произведение определяется для двух векторных операндов, в результате чего получается скаляр. Поэтому скалярное произведение тоже не является групповой операцией. Скалярное произведение двух векторов a и b обозначается a. b или (a, b) и имеет следующие свойства: (коммутативность): а. b = b. a (дистрибутивность): а. (b + c) = a. б + а. с Например, скалярное произведение для 3-кортежей определяется следующим образом:
В качестве применения этих законов давайте докажем простую, но интересную идентичность.
Два вектора, скалярное произведение которых равно нулю, называются ортогональными или перпендикулярными. Например, ортогональными являются следующие пары 3-кортежей: a и (0, 1, 0), (1, 0, 1) и (2, 1, -2). Для ортогональных векторов мы имеем следующее обобщение теоремы Пифагора:
Если мы введем длину (также называемую нормой) вектора a как || а||2 = а. а, тогда теорема Пифагора допускает более условный вид:
Тождество (*) является обобщением закона косинуса. На самом деле (*) является одной из причин того, что угол между двумя векторами определяется следующим образом:
|