Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2 простых сомножителя. Зададим ряд чисел Ns (s - нуль и натуральное число), где на каждом шаге к Ns прибавляются числа в порядке
возрастания: для вычисления Ns к Ns−1 прибавляется число (2s-1).
Тогда итеративно вычислим элементы Ns по формуле Ns=Ns-1+2s-1:
N0=n
N1=N0+1
N2=N1+3
N3=N2+5
……
Ns=Ns-1+2s-1
……
Прибавляемые к Ns числа являются членами арифметической прогрессии:
- начальный элемент равен a0=1,
- последний - as=2s-1,
- число членов - m=s
- шаг прогрессии равен 2.
Тогда сумма чисел прибавленных к n равна (по формуле суммы арифметической прогрессии) Sпрогрес= (a1 +as )m/2=(1+2s-1)s/2=2s2/2= s2.
В результате элемент Ns равен Ns = N0 + Sпрогрес = n + Sпрогрес= n + s2.
Предположим, что из Ns извлекается нацело квадратный корень, то есть Ns = t2, где t - некоторое натуральное число, тогда Ns = t2= n + s2 Þ n = Ns − s2 = t2 − s2.
Таким образом, если при некотором s будет возможно извлечение нацело квадратного корня из Ns = t2, то исходное число n раскладывается как
n=(t2−s2)=(t−s)(t+s).
ù=n -9 é 2 2
Если в диапазоне для s: 1≤s≤ úû 6
ëêне будет найдено t , где из t
нацело извлекается квадратный корень, то процесс поиска двух сомножителей числа n завершается - число n является простым или алгоритм не применим для него.
Описание алгоритма.
На вход подается натуральное число n.
На выходе: 2 сомножителя числа n или ответ о неприменимости алгоритма для числа n.
1. Ввод числа n. Если n<9, то задача данным алгоритмом не решается. Выход.
2. N=n.
ùn -9 é
3. Для "s =1, úû
6 êë
выполнить:
3.а. N=N+2s-1.
3.б. t =] N [ .
3.в. Если t2=N, то
вывод чисел (t-s) и (t+s); Выход из алгоритма.
4. Разложить число n не удалось. Выход из алгоритма.
Пример 1.4. Пусть n = 69.
Таблица 1.4. Трассировочная таблица
Шаг, s | ù=n -9 é Условие:s £úû 6 êë? | N = N+2s-1 | t =] N [ | Условие: t =N? |
да: 1≤10 | нет: 64≠70 | |||
да: 2≤10 | нет: 64≠73 | |||
да: 3≤10 | нет: 64≠78 | |||
да: 4≤10 | нет: 81≠85 | |||
да: 5≤10 | нет: 81≠94 | |||
да: 6≤10 | нет: 100≠105 | |||
да: 7≤10 | нет: 100≠118 | |||
да: 8≤10 | нет: 121≠133 | |||
да: 9≤10 | нет: 144≠150 | |||
да: 10≤10 | да: 169=169 |
ù=n -9 é
N0=n=69; максимальное число шагов:
s £úû 6
êë=10 . Шаги работы
алгоритма представим в виде трассировочной табл. 1.4.
Из числа N10= 169 можно извлечь квадратный корень: t2=13. Тогда
n = (t2 − s2) =(t − s)? (t + s)=(13-10)? (13+10) = 3? 23.
Т.е. число 69 раскладывается на два числа: 3 и 23.
Пример 1.5. Пусть n = 23.
ù=n -9 é
N0 = n = 23; максимальное число шагов: s ≤ úû 6
ëê= 2.
Шаги работы алгоритма представим в виде трассировочной табл. 1.5.
Таблица 1.5. Трассировочная таблица
Шаг, s | n -9 Условие: s £ ? | N = N+2s-1 | t =] N [ | Условие: t 2 =N? |
да: 1≤2 | Нет: 16≠24 | |||
да: 2≤2 | Нет: 25≠27 | |||
нет: 3>2 | - | - | - |
Таким образом, число 23 не раскладывается алгоритмом Бухштаба на 2
простых сомножителя.