Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2), страница 6

Может ли существовать более одного решенияу 4.5.4. Разложение на простые ыножители В основу ряда вычислительных методов, которые рассматривались в этой книге, положен тот факт, что любое положительное целое число и можно однозначно выразить в виде и = р!рз " рм р1 < рз « " рь (1) где каждое ре — простое число. (В случае, когда и =- 1, это равенство выполняется при ! =- О.) К сожалению, довольно сложно найти это разложение на простые множители илн определить, является ли число и простым. Общеизвестно, что разложить на простые множители большое число значительно труднее, чем найти наиболыний общий делитель двух больших чисел т н п. Поэтому там, где это возможно, следует избегать разложения больших чисел на простые множители.

Но, учитывая, что разработан целый ряд оригинальных методов, позволяющих ускорить процесс разложения чисел на простые множители, проанализируем некоторые из 3тнх методов. [Всесторонний исторический обзор методов разложения чисел на простые множители, известных до 1950 года, выполнен Х. К. Уильямсом (Н. С. %!!!!щпэ) и Дж. О. Шэллитом (3. О.

Впа)1!1)„Ргос. Вущр. Аррбес) Май. 48 (1993), 481-531,] Деление н разложение на множители. Прежде всего рассмотрим самый очевидный алгоритм разложения на простые множители. Если число и > 1, то его можно делить на последовательные простые числа р = 2, 3, 5, ... до тех пор, пока ке будет обнаружено наименьшее число р, для которого и щод р = О. Тогда р н будет наименьшим простым множителем числа и. Тот же процесс можно применить к числу п е — и/р и попьггаться разделить полученное значение числа п на р и на ббльшие простые числа. Если на некотором этапе обнаружится, что и щи р 14 О, но [и/р) < р, можно сделать следующий вывод: число и — простое, так как если п не является простым числом, то в силу равенства (1) должно быть и > р1з.

Но нз условия р1 > р следует, что рз > (р+ 1)з > р(р+ 1) > рз+ (ц пик)р) > [и/р1р+ (и пнк1 р) = и. В результате получаем следующую процедуру. рис. 11. Простой алгоритм разложения на множители. Алгоритм А (Разложение ма вросшие ммолснтаяи нршем деленна). Поданному положительному целому числу Х этот алгоритм (рнс. 11) находит простые множители р~ < рт < < ?ь числа Ж в соответствии с равенством (1).

В этом методе используется вспомогательная последовательность пробных делителей (2) 2 = 4) < 4 < Из < пз < ") которая включает в себя все простые числа < 4Х (и, если это удобно, может содержать числа, не являющиеся простыми). Последовательность чисел о; должна также содержать по крайней мере одно значение, такое, что Ие > ~/Х, А1.

[Начальная установка.) Присвоять г е- О,?г е- О, и е- Х. (В ходе выполнения алгоритма переменнгяе 1,?г, и подчинены следующим условиям: "и = Ю/р~... р~ и и не имеет простых множителей, меньших йе" ) А2. [в = 1?) Если н = 1, алгоритм заканчивается. АЗ. [Разделять.[ Присвоить д е- [и/оЦ, г +- и щи Ие. (Здесь 4 и г — соответственно частное и остаток от деления числа и на оа.) А4. [Остаток ранен нулю?) Если г ~ О, то перейти к шагу Аб. А5.

[множитель найден.) ъ'велнчить г на 1 и присвоить рг +- иы и +- 4, Возвратиться к шагу А2. Аб. [Частное мачб?) Если 4 ) ды увеличить Й на 1 и возвратиться к шагу АЗ. АТ. [п — простое число.) Увеличить г на 1, присвоить р~ +- н и завершить выполнение алгоритма. 1 В качестве примера алгоритма А рассмотрим разложение на простые множители числа Х = 25852. Сразу же находим, что Х = 2 ° 12926; следовательно, р~ = 2. Далее, 12926 = 2 6463, юк что рт = 2, Но теперь число и = 6463 не делится на числа 2, 3, 5, ..., 19; находям, что и = 23 281: значит„рз = 23. В итоге имеем 281 = 12 23+ 5 н 12 < 23, т.

е. ре = 281. В рассмотренном примере для определения простых множителей числа 25852 нужно было выполнять 12 операций деления. С другой стороны, при разложении на простые множители чуть меньшего числа 25 849 (которое оказывается простым) пришлось бы затратить не менее 38 операций деления. Это показывает, что время выполнения алгоритма А приблизительно пропорционально шах(рс ы Я ). (При г = 1 эга формула справедлива, если покожить, что ре = 1) Последовательность Не, Иы пю ... пробных делителей, используемал в алгоритме А, можно просто считать последовательностью чисел 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ..., члены которой, кроме первых трех, получаются посредством попеременного увеличения предыдущих на 2 и 4.

Данная последовательность содержит все числа, не являющиеся кратными 2 или 3; при этом она содержит и такие числа, как 25, 35, 49 и т. д., не являющиеся простыми. Тем не менее алгоритм будет давать правильный результат. Если из этой последовательности убрать числа 30т х 5 при т > 1, исключая тем самым как ложные простые все чнгла, кратные пяти, то можно сэкономить до 20% времени выполнения алгоритма. Исключив из рассмотрения числа, кратные 7, можно сократить список еще на 14% и т. д.

Для управления выбором пробных делителей можно воспользоваться какой-нибудь компактной таблицей. Если известно, что Х малб, резонно иметь таблицу всех необходимых простых чисел как часть программы, Например, если А! меньше миллиона, то нужно включить 168 простых чисел, меньших 1000 (к этому списку нужно еще добавить значение 4ьэ = 1000 как заключительного члена для случая, когда число А' окажется простым, ббльшим 997з), Такую таблицу можно получить при помощи короткой вспомогательной программы (см., например, алгоритм 1.3.2Р или упр.

8). Сколько пробных делителей необходимо для алгоритма А? Пусть я(х) — количество простых чисел < х, так что я(2) = 1, я(10) = 4. Асимптотическое поведение этой функции интенсивно изучалось многими величайшими математиками, начиная с Лежандра (1 ейепйе), который исследовал эту проблему в 1798 году. Кульминацией многочисленных достижений в решении этой проблемы в течение 19 века явилось доказательство в 1899 году Шарлем де Ла Валле Пуссеном (Сваг!еэ г(е 1.а ЪЪ!!ее Ропэз!и) того факта, что для некоторого А > 0 (3) (Мегп. Сопгоппел Асад. Ноу.

Ве)йк1пе 59 (1899), 1-74; см. также 3. Набюпагг), Ви!!. 5ос. Май. Ргапсе 24 (1896), 199-220.) Интегрирование по частям дает х х 2!х г!х / х я(х) = — + — + — '+" + ' +О ~ 1п х (1п х)з (!и х)з (!и х)'+' 1, (!ой х) "+з / (4) для всех фиксированных г > О. В дальнейшем остаточный член в формуле (3) последовательно уточнялся. Например, его можно заменить следующим выражением: 0(хехр( — А(!ойх)з~ь?(!ой!ойя)'1ь)).

[См. А. %а)бкх, !теу!есле Ехропепба!эиттеп ш с(ег пепегеп ЯаЫепйеог!е (Вег!ш, 1963), СЬар!ег 5.) В 1859 году Бернард Риман (Вепйагб В1ешапп) предположил, что где б(х) = ) * й/!и й Эта формула хорошо согласуется с выполненными расчетами при выборе х в подходящем диапазоне. Формула Римана 168.3 78527.4 50847455.4 37607910542.2 29844570495886.9 2473995428423949 4.4 ? (х) 176.6 78626.5 50849233.9 37607950279.8 29844571475286.5 24739954309690414.0 х х(х) 103 168 1Ов 78498 10э 50847534 !О'з 37607912018 1Оы 29844570422669 10га 24739954287740860 (См. упр.

41,) Однако проблема распределения простых чисел не так проста, и в 1914 году Дж. Э. Литтлвуд (Л. Е. ?.!гс!евчнк?) показал, что существует такая положительная константа С, что неравенство х(х) > Ь(х) + Ст/х?ой!ой!ойх/1ойх справедливо для бесконечно многих значений х, чем опроверг предположение Римана (5), (См.

Нагбу, ?лсс!ек'оос$, Асга Магп. 41 (1918), 119-196.) Результат Литтлвуда показал, что в простых числах заложено что-то мистическое н что для действительного понимания законов их распределения необходимо разработать глубокую математическую теорию. Римки высказал намного более конструктивное предположение, известное как "гппотеза Римана", согласно которому комплексная функция ь(х) равна нулю толью тогда, когда ее действительная часть равна 1/2, за исключением тривиальных случаев, когда х есть отрицательное целое число.

Если эта гипотеза верна, то из нее следует я(х) = Цх) + 0(ь/х !ой х); см. упр. 25. Ричард Брент (???снап? Вгеп!) выполнил численную проверку гипотезы Римана для всех "малых*' значений г, использовав метод Д. Г. Лемера (?!. Н.?.еЬшег) и показав, что функция ь(х), мнимая часть которой принадлежит интервалу О < Зз < 32585736.4, имеет точно 75 000 000 нулей; для всех этих нулей ЗЬ = 1 н ~'(э) ~ О. (Ма!й. Сснпр. 33 (1979)., 1361-1372.) Для анализа поведения алгоритма А в среднем необходимо выяснить, насколько болыпим может оказаться наибольший простой множитель рс. Этот вопрос был впервые исследован Карлом Дикманом (Каг! Рйс1ппап) (АгЫг ?бг Мак, Аз!гоп, ос?! Рук 22А, 10 (1930), 1-14), который проанализировал вероятность того, что случайное целое число, принимающее значения между 1 н х, будет иметь наибольший простой множитель < х".

Дикман показал, что эта вероятность прн х -э оо стремится к предельному значению Р(а), где Р может быть вычислено в результате решения функционального уравнения 7 г ! 1 й г"(а) = ! Г( — ) — при О<а <1; Г(а) =! при а>1. (6) Ь вЂ” д~ Ход его рассуждений был примерно следующим. Для заданного 0 < ! < 1 количество целых чисел, меньших х, наиболыпие простые множители которых расположены между х' и х'+'и, равно хР'(!) Й. Количество простых чисел р в этом интервале равно х(х'+ш) —;г(х') = я(х'+ (1п х)х' Й) — к(х') = х' Ф/й Для каждого такого р количество целых чисел и, таких, что "пр < х и наибольший простой множитель числа и не превышает р", равно количеству чисел, для которых и < х' ' и наибольший простой множитель не превышает (х1 ')'Д' о, т. е.

х' 'г (1/(1 — 1)). Следовательно, хгч(1) ег = (х' ог/г) (х' 'г (г/(1 — г)) ) и уравнение (6) получается посредством интегрирования последнего уравнения, Этому эвристическому доводу может быть придана строгость. В. Рамасвамн (У.