Как найти минимальный нетривиальный делитель

Найти наименьший нетривиальный делитель натурального числа

Формулировка. Дано натуральное число. Найти его наименьший нетривиальный делитель или вывести само это число, если такового нет.

Решение. Задача решается аналогично предыдущей. При этом необходимо начать обычный цикл с увеличением, при котором переменная цикла i изменяется от 2 до n (такая верхняя граница нужна для того, чтобы цикл всегда заканчивался, так как когда i будет равно n, выполнится условие n mod i = 0). Весь остальной код при этом не отличается.

Факторизация чисел и сумма неизвестных делителей. Часть IV

Так в Г 2± – модели НРЧ в клетке ( ) всегда лежит сумма делителей N, если само число N помещено в клетке ( ). Кроме этого, в клетке ( ) лежит значение функции Эйлера СННЧ N, если его собственные делители простые числа.

В теории чисел известны две формы представления (моделей) числа: аддитивная и мультипликативная на основе ОТА. Эти формы (при аддитивном представлении числа суммой членов отрезка непрерывной последовательности нечетных чисел) тесно связаны. Число слагаемых в сумме равно меньшему делителю, а среднее слагаемое — большему. Это не так, если аддитивная форма представляет произвольное разбиение числа на части. Например, в 1-ом случае 105 =33+35+37 =3·35 и 105 = 60+40 +5 ≠3·40 — во 2-ом.

Поводом для написания этой работы послужило стремление автора познакомить читателей с подходом к задаче факторизации чисел на основе факта, открытого автором при изучении модели натурального ряда чисел (НРЧ), а также с результатом Л. Эйлера,
$inline$σ(N) = σ(N-1)+σ(N-2)-σ(N-5)-σ(N-7)+σ(N-12)+σ(N-15)-$inline$
, который состоит в том, что для произвольного СННЧ N можно вычислить сумму σ(N) его делителей, не располагая значениями самих делителей. Это положение граничит с мистикой, но оказывается такое возможно при наличии качественных моделей НРЧ и отдельного числа.

Определенным стимулом явилась также публикация Пшеннова А.В. в Интернете, где приводится некоторый фактический материал по делителям чисел и их суммам. Конечно,
основной причиной является наблюдение, сделанное автором самостоятельно, при изучении созданной и разрабатываемой им оригинальной модели натурального ряда чисел (НРЧ). Приведу краткое описание модели, которая ранее уже рассматривалась здесь .

Таблица М — Модель (плоскостная) натурального ряда чисел

символами в модели обозначены соответственно номера строк и столбцов.

В модели использовано известное положение о том, что в любой клетке СННЧ N = а·b представимо разностью квадратов двух целых чисел ( ) разной четности, которые выбираются специальным образом, т.е. и а, b играют роль диагоналей, пересекающихся в этой клетке модели.

Сущность наблюдения в Г 2± – модели НРЧ (таблица М) состоит в следующем. Располагая в модели координатами клетки, легко определяются значения чисел в них, но обратная задача трудно решаемая. Допускаем, что координаты клетки заданного СННЧ N известны.

Сумму делителей числа N из клетки ( ) обозначают σ(N). Cумма σ(N) этих двух (а, b) неизвестных нетривиальных делителей, а также тривиальных делителей 1 и самого N, определяется (вычисляется) в модели, как значение числа в другой клетке с координатами ( ), в то время как само число N помещается в клетке ( ), что легко показывается. Установлены, сформулированы и доказаны две новые теоремы.

Теорема 1. Если в клетке ( ) Г 2± – модели НРЧ содержится СННЧ N = а·b, где а,b -собственные делители играют роль номеров короткой и длинной диагоналей, пересекающихся в этой клетке, то в строке ниже под этой клеткой в клетке ( ) содержится сумма σ(N) делителей СННЧ N. (положение N задано, а и b неизвестны).

Доказательство. Значение любой клетки Г 2± – модели НРЧ по основному соотношению модели равно , где в скобках соответственно приведено произведение — номеров диагоналей длинной и короткой, пересекающихся в этой клетке и выполняющих роль делителей N=аb. Под клеткой со значением N помещается клетка, значение в которой равно произведению диагоналей, увеличенных на 1, т.е. (а+1)(b+1)=а·b+а+b+1=σ(N), раскрывая скобки, получаем сумму делителей. Этим доказательство завершается.

В этом равенстве а·b+1=N+1, а разность σ(N)-N-1=а+b — есть сумма только собственных делителей N. Названные зависимости легко могут быть выражены через переменные модели ( ), так как а = ( ) и b=( ), тогда .
Здесь же отметим и еще одно наблюдение для которого справедлива следующая

Теорема 2. Если в клетке ( ) Г 2± – модели НРЧ содержится СННЧ N = а·b, где а,b -собственные делители играют роль номеров короткой и длинной диагоналей, пересекающихся в этой клетке и являющиеся простыми нечетными числами, то в строке выше над этой клеткой в клетке ( ) содержится функция Эйлера φ(N) СННЧ N. Положение N задано, а и b неизвестны.

Доказательство. Здесь повторяется положение предыдущей теоремы, но для клетки выше изменяются знаки. Над клеткой со значением N помещается клетка, значение в которой произведение номеров диагоналей, уменьшенных на 1, т.е. φ(N)=(а-1)(b-1) = а·b -а-b+1. Этим равенством доказательство теоремы завершено.
Результаты обеих теорем (показано ниже) могут быть применены в атаках на шифр RSA.

Из второй теоремы следует, если а и b простые нечетные числа-нетривиальные делители числа N, то произведение φ(N) = (а – 1)( b – 1) и разность являются теоретико-числовой функцией Эйлера для составного числа N.
Приведем вид решетчатой функции σ(N) суммы делителей в зависимости от числа N. По оси ординат расположим числа N, а по оси абсцисс σ(N) сумму их делителей (1≤N≤1000).

На графике отчётливо просматриваются несколько наклонных линий из точек, имеющих сходство с прямыми, например, нижняя линия соответствует суммам делителей простых чисел. Верхняя граница – это наиболее сложные числа (имеющие наибольшее количество делителей) — это не прямая, но и не парабола. Возможно – это показательная функция вида ( ).

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

Процесс продолжается до тех пор, пока это оказывается возможным. Как только все возможности разложения всех делителей N исчерпаны, процесс факторизации прекращается. Найденные простые факторы можно перемножить между собой, что должно дать в результате вновь исходное число N.

Этот факт служит подтверждением правильности найденного решения.
Чтобы количественно почувствовать и оценить зависимость σ(N) – суммы делителей от числа N покажем последовательность таких сумм для первых ста натуральных чисел N (см. таблицу 1):

Таблица 1. Суммы σ(N) делителей натуральных чисел, полученные Эйлером.

Из приведенных весьма ограниченных данных видим, что для простых чисел σ(N)=N+1, что некоторые различные числа (46, 55, 71) имеют совпадающие значения σ(N) = 72, а некоторые N не являются суммами делителей ни одного из натуральных чисел.

В теории чисел известны следующие результаты. Найти сумму всех делителей натурального числа можно с использованием канонического разложения N, если оно известно. Легко найти простым перебором σ(N) для небольших натуральных чисел, например, .

Но при достаточно больших значениях N нахождение всех делителей, а тем более их суммы становится затруднительным. Совсем другое дело, если уже известно, каноническое разложение числа N.
Делителями N являются все числа, для которых $inline$0 ≤ β_s ≤ α_s , s = 1(1)k$inline$ . Ясно, что σ(N) представляет собой сумму всех таких чисел при различных значениях показателей .

В работе предлагается один из возможных вариантов построения алгоритма решения за-дачи факторизации, который не зависит или слабо зависит от разрядности факторизуемого числа. В основу алгоритма поиска решения положен принцип использования суммы двух нетривиальных делителей (факторов) натурального числа.

Ясно, что существуют составные натуральные числа, образованные произведением всего лишь двух простых чисел (RSA числа). Это, вообще говоря, частный для теории чисел случай, но очень важный для практики. В общем случае оба делителя а и b – составные числа. Для лучшего понимания идеи такого алгоритма факторизации ниже приведем числовые примеры, рассматриваемые в рамках приведенной Г 2± – модели НРЧ (табл. М).

Пример 1.
Найти разложение заданного составного натурального числа N на множители а и b, если а и b неизвестны, а их сумма σ(N)=а + b известна.
Данная задача может быть сведена к нахождению решения системы двух алгебраических уравнений с двумя неизвестными. Чтобы исключить тривиальные решения (делители) вычтем их из заданной σ(N) суммы делителей .

В рассматриваемом примере решением задачи факторизации числа N являются значения а и b, удовлетворяющие замкнутой системе двух алгебраических уравнений:
,
.

Здесь σ(N) обозначает сумму всех делителей N, которая полагается известной, а вычисляется и представляет собой сумму лишь двух нетривиальных делителей простых или составных чисел. Как находить значения таких сумм σ(N) и будет показано позже.

Выполним преобразование записанной системы двух уравнений путем исключения переменной b. Это приводит к одному квадратному уравнению , корни которого и есть искомые делители числа N. Воспользуемся теоремой Виета. Тогда корни квадратного уравнения определяются соотношением

Таким образом, задача факторизации числа в рассматриваемой ситуации будет успешно решена, если для числа N предварительно будет определена σ(N) сумма делителей.

Пример 2 (числовой с двумя простыми делителями). Задано N = a·b = 301, для которого известна клетка ( ) его размещения в Г 2± – модели НРЧ. Требуется определить cумму всех делителей σ(N) числа N, вычислить функцию Эйлера и факторизовать N.

Решение. Воспользуемся результатом Эйлера для подсчета суммы собственных делителей
$inline$σ(N) = σ(N-1)+σ(N-2)-σ(N-5)-σ(N-7)+σ(N-12)+σ(N-15)-$inline$

$inline$σ(300)+σ(299)-σ(296)-σ(294)+σ(289)+σ(286)-σ(279)-σ(275)+σ(266)+$inline$
$inline$+σ(261)-σ(250)-σ(244)+σ(231)+σ(224)-σ(209)-σ(201)+σ(184)+σ(175)-$inline$
$inline$-σ(156)-σ(146)+σ(125)+σ(114)-σ(91)-σ(70)+σ(54)+σ(41)-σ(14)-σ(0)=$inline$

Уже отмечалось, что для простого числа q сумма σ(q)=q+1 равна сумме делителей q и 1. Поэтому при $inline$N = 301 =7·43, σ(301)=σ(7)·σ(43)=8·44 =352 $inline$

Располагая моделью Г 2± этот результат получается вычислением в одной клетке. Находим , сумма неизвестных а и b делителей Находим делители $inline$а_<1,2>=50/2±(25^2-301)^ ½ =25± 18; а = а_1=43, b=а_2 =7.$inline$ Покажем как связаны делители и координаты клетки

Наконец, вычислим значение функции Эйлера
Ответ: корни уравнения-делители N реализуют факторизацию. Проверка N = a∙b = 43∙7 = 301,

Убедимся, что в терминах переменных сумма делителей совпадает с вычисленной

Вычислим при найденных значениях a и b, функцию Эйлера
. Значения функции Эйлера, вычисленные двумя способами, совпали.

Пример 3 (числовой с одним простым и одним составным делителем). Задано N = 147, для которого сумма всех делителей σ(N) = σ(147) = 1+3+7+21+49 +147= 228. Но для четырех делителей числа N сумма равна 1 + а + b + 147, σ(N) = 176. Здесь а=21 и b=7 неизвестные делители, формирующие значение N. Требуется факторизовать число N.

Решение. Находим .
$inline$а_<1,2>=28/2 ±(196 — 147)^ ½= 14 ± 7.$inline$ Корни найдены Установим связь корней с переменными .
Ответ: Корни уравнения . Проверка a∙b = 21∙7 = 147

В этом примере один из делителей а=21 оказался составным числом, но именно это число и является слагаемым в сумме делителей, что видим в модели (табл. М строки 14,15; столб. 7) .

В примерах 2 и 3 рассмотрены задачи, в которых в качестве исходных данных задано число N и клетка его размещения. Требовалось факторизовать число N, т.е. отыскать делители. Для факторизации привлекалась модель НРЧ и в ее клетках отыскивалась сумма делителей σ(N) и функция Эйлера φ(N), когда делителей (собственных) было всего два и они оба были простыми числами.

Существует симметричная относительно исходных данных задача, в которой известна сумма N+1 кратных делителей N = pq и клетка в Г 2± – модели НРЧ с координатами ( ), в которой лежит кратное целому числу sN произведение . Само число N лежит в последней клетке строки x1 с кратным произведением в Г 2- – модели НРЧ. Требуется факторизовать составное число N.

Пример 4. Заданы составное число N=pq =77, сумма , коэффициенты целые числа, координаты клетки ( ) с кратным произведением числа . Требуется факторизовать N, т.е. определить p и q делители N.

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

Пример 5. Если – различные простые числа, то σ(N) для различных их комбинаций имеет формулы:

$inline$σ(a·b·c·d) = σ(a)·σ(b)·σ(c)·σ(d),$inline$

, и вообще,
.

Пользуясь этими соотношениями, можно записать
$inline$σ(a^q·b^w·c^e·d^r) = σ(a^q)·σ(b^w)·σ(c^e)·σ(d^r). $inline$
Пусть $inline$N = p_1^<α_1>×…× p_k^<α_k>$inline$ по формуле конечного числа членов геометрической прогрессии приходим к равенству

Следующий результат в виде ряда для σ(N) получил Л. Эйлер, который записал сомножители N в многочленном представлении и раскрыл скобки в произведении многочленов
$inline$σ(N) = σ( p_1^<α_1>×…× p_k^<α_k>))$inline$ =
.

Ряд Эйлера

Этот ряд обеспечивает вычисление суммы делителей составного числа N, не зная ни числа делителей, ни их значений.
$inline$σ(N) = σ(N-1)+σ(N-2)-σ(N-5)-σ(N-7)+σ(N-12)+$inline$

Аналогичный результат получен в рамках исследования Г 2± – модели НРЧ (Теоремы 1 и 2)

Пример 6. Необходимо вычислить σ(360), при известном каноническом разложении на множители числа. По формулам теории чисел это легко вычисляется.
.

Эта задача по формулам не решается, если для N отсутствует каноническое разложение.
Ряд Эйлера позволяет свести задачу к решению системы алгебраических уравнений как в примерах 2 и 3. Но возникает ряд проблем, хотя и преодолимых. Привлечение модели НРЧ (табл. М) снимает часть затруднений, но создает свои.

Описание и использование ряда Эйлера при расчетах σ(N)

Пусть задано нечетное число N, которое требуется факторизовать, и известно, что N = pq, где p и q простые числа. Делителями N кроме p и q являются также 1 и само число N. Если известна сумма p + q = σ(N), то, как показано ранее, задача факторизации легко решается. Далее поясним как находятся значения σ(N) без знания делителей.

Рассмотрим две числовые последовательности: а) натуральных чисел;
б) нечетных чисел.
а)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3738…
б) 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49……

вторая последовательность начинается не 1, а числом 3.
Сольем эти две последовательности в одну, обозначив ее s, чередуя числа из последовательностей а) и б), а также выполним нумерацию элементов s сформированного ряда.

Таблица 2 – Совмещенные последовательности ряда нечетных и натуральных чисел.

Нечетные номера получают элементы из натурального ряда, а четные – из ряда нечетных чисел (при начале отсчета элементов s от единицы и наоборот, если начать отсчет номеров от нуля).

Использование ряда s предполагает возможность вычисления любого его элемента по текущему номеру или восстановление текущего номера по известному значению элемента ряда. Анализ ряда s показывает, что для элементов нечетного ряда их значение на единицу больше текущего номера, а значения элементов из натурального ряда равны половине увеличенного на единицу порядкового номера. Следующие примеры проясняют эти утверждения.

Пример 7. Порядковый номер элемента ряда s равен 30. Определить значение s(30).
Так как 30 ≡ 0(mod2), т.е. номер – четное число, то s(30) принадлежит ряду б) нечетных чисел и равно s(30) = 30 + 1 = 31.

Пример 8. Порядковый номер элемента ряда s равен 37. Определить значение s(37).
Определяем четность номера 37 ≡ 1(mod2). Номер нечетный, следовательно, число с этим номером принадлежит натуральному ряду а) и его значение
s(37) = (37 + 1)/2 = 19.

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

Пример 9. Значение элемента ряда s = 13. Определить порядковые номера для s-1(13).
Если s принадлежит натуральному ряду чисел, то его номер является нечетным числом и большим из двух возможных.
Таким образом, №натур(s) = 2s – 1 = 2∙13 – 1 = 25.

Если s принадлежит ряду нечетных чисел, то его номер – четное число и определяется по формуле № нечетн(s) = s – 1 = 13 – 1 = 12. Это меньший номер из двух. Оба номера связаны простым соотношением
№натур(s) – № нечетн(s) = (2s – 1) – (s –1)= s = 25 – 12 = 13.

Разность номеров равна значению s. Таким образом, поведение элементов ряда s, т.е. значения и занимаемые позиции устанавливаются достаточно простыми соотношениями.
Как этими фактами можно воспользоваться при решении задачи факторизации?
Оказывается, ряд s является рядом разностей смежных элементов другого ряда k(i), открытого Эйлером, и по известному ряду s ряд k(i) можно восстановить.

Таблица 3 – Последовательность нумерованных чисел k(i) ряда Эйлера

k(1) =1, k(2) = k(1) + s(1) = 2, k(3) = k(2) + s(2) = 2 + 3 = 5,
k(4) = k(3) + s(3) = 5 + 2 = 7, k(5) = k(4) + s(4) = 7 + 5 = 12 и т. д… в общем виде
k(i + 1) = k(i) + s(i), i = 1(1)…, k(1) = 1.

Ряд k(i) был открыт Л. Эйлером, который указал на его применимость к решению задачи определения сумм делителей натуральных чисел в формуле:
σ(N)=σ(N-k(1))+σ(N-k(2))-σ(N-k(3))-σ(N-k(4))+σ(N-k(5))+σ(N-k(6))-σ(N-k(7))-
-σ(N–k(8))+= … = σ(N-1)+σ(N-2)-σ(N-5)-σ(N-7)+σ(N-12)+σ(N-15)-σ(N-22)-σ(N–26)+ …

При выполнении расчетов σ(N) для аргумента функции σ(N) вычисляются разности
N — k(i), если σ(N) обозначает любой член этой последовательности, а σ(N — 1),
σ(N — 2), σ(N — 5)… предшествующие члены, то σ(N) всегда можно получить по нескольким предыдущим членам:
σ(N)= σ(N — 1)+ σ(N — 2)- σ(N — 5)- σ(N — 7)+ σ(N — 12)+σ(N — 15)- σ(N — 22)- σ(N – 26)+ …

Знаки «+» и «–» в правой части формулы попарно чередуются.
Возникают еще вопросы. Когда необходимо ограничить бесконечный ряд, остановиться? Как определить значение в точке останова?

Алгоритм перебора чисел

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.

отрезок большой и программа работает эффективно из-за строки

как это работает с математической точки зрения?

Если рассмотреть разложение n = p₁ e₁ p₂ e₂ p₃ e₃ . (где p_i — различные простые), то можно догадаться что общее число делителей n равно (e₁ + 1)(e₂ + 1)(e₃ + 1). . В это число входят единица и само n, конечно.

В задаче требуется найти числа с тремя нетривиальными делителями. Всего делителей тогда будет пять. Пять — простое число, единственный способ представить его в виде произведения — это оно само. Следовательно число с тремя нетривиальными делителями (с пятью делителями вообще) имеет разложение вида p 4 . То есть, мы ищем четвертые степени простых чисел, а максимальным нетривиальным делителем будет куб p 3 .

Условие round(sqrti) == sqrti выполняется только для целых чисел, которые являются квадратами других целых чисел. А так как нам интересны четвёртые степени (которые и квадраты тоже), то условие эффективно сужает число кандидатов.

Ваш пример работает у меня около сорока секунд. Но можно сделать лучше.

Код который перебирает четвёртые степени простых работает 0.05с. Проверка простоты кандидатов написана просто и не эффективно, так как самое большое число, которое надо будет проверять на простоту — 122 (корень четвёртой степени из правого конца диапазона):

Решение задачи 25 из ЕГЭ по Информатике в PascalABC.NET

Модуль school , встроенный в последние версии PascalABC.Net, содержит реализацию алгоритмов, часто встречающихся в школьных задачах. Их использование сильно сокращает программный код и упрощает решение задачи. Каждая реализация в основном имеет два формата – для вызова в виде функции и для записи в точечной нотации. Рассмотрим типовые для номера 25 задачи ЕГЭ и их решение двумя способами: без использования функций модуля school и с его помощью.

Нахождение делителей числа

При нахождении нетривиальных делителей натурального числа ? (которые отличны от 1 и самого числа ?) часто предлагается перебирать числа из диапазона от 2 до [?/2] (скобки [] обозначают операцию взятия целой части числа), поскольку на интервале от [?/2]+1 до ?−1 у числа ? нет делителей. При таком подходе для нахождения делителей, например ?=10000 придется перебрать 4999 чисел (от 2 до 5000).

Перебор делителей числа ? можно оптимизировать, учитывая, что наименьший из пары делителей, таких что ?∗?=?, не превышает квадратного корня из ?; нужно только аккуратно обработать случай, когда число ? представляет собой квадрат целого числа. В этом случае для нахождения делителей, например ?=10000 придется перебрать уже 99 делителей (от 2 до 100=sqrt(10000)).

Получается, что для определения количества делителей числа ? достаточно перебирать только числа от 2 до √N; если очередной делитель ? – это точный квадратный корень, добавляем в список делителей только один делитель, если нет – то добавляем пару делителей (?, [?/?]). Потом (или сразу) необходимо добавить к списку делителей единицу и само число ?.

PascalABC модуль school: список делителей числа

В PascalABC.Net для получения списка . содержащего все натуральные делители числа ?, включая 1 и ?, могут быть использованы:

• функция . (?), которая в зависимости от типа ?, возвращает значение типа . <. > или . <. 64>;
• расширение . – делает то же самое.

Задача

Вывести все делители натурального числа ?.

Способ 1 (без school)

Способ 2 (используя модуль school)

Разложение числа в произведение простых множителей

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

PascalABC модуль school: разложение числа ? на простые множители

В PascalABC.Net для получения списка . содержащего все простые делители числа ?, могут быть использованы:

• функция . (?) – выполняет разложение числа ? типа . или . 64 на простые множители, результат помещается в список . ;
• расширение . делает то же самое.

Задача

Разложить натуральное число ? в произведение простых множителей.

Рассмотрим реализацию решения задачи без использования функции . (?) модуля ??ℎ. а затем с её использованием.

Способ 1 (без school)

Способ 2 (используя модуль school)

Другие полезные функции модуля school

PascalABC модуль school: простые числа

• функция . (?) – возвращает список . содержащий простые числа на отрезке [2; ?];
• функция . (?) – возвращает список . содержащий первые ? простых чисел;
• расширение . – возвращает . если ? – простoе и . в противном случае. Переменная ? должна быть типа . или . 64.

PascalABC модуль school: нахождение НОД и НОК пары чисел a и b

• функция НОД(. ) – возвращает НОД типа . или . 64;
• расширение ?.НОД – возвращает НОД для кортежа ?=(. ) с данными типа . или . 64;
• функция НОК(. ) – возвращает НОК типа . 64;
• функция НОДНОК(. ) – возвращает кортеж вида (НОД,НОК) для пары чисел ? и ? типа . 64.

PascalABC модуль school: список цифр числа

Получение списка . содержащего все цифры числа ? в порядке их следования слева направо:

• функция . (?) – возвращает список типа . <. 64>;
• расширение . делает то же, возвращая список типа . <. > или . <. 64>.

Решение типовых задач ЕГЭ

Демо к ЕГЭ 2021

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.

Ответ:

3 58153
7 24923
59 2957
13 13421
149 1171
5 34897
211 827
2 87251

Способ 1 (без school)

Способ 2 (используя модуль school и лямбда-выражения)

Статград вариант ИН2010103

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.

Ответ: 1225043; 1295029; 1442897

Способ 1 (без school)

Способ 2 (используя модуль school)

Способ 3 (используя модуль school и лямбда-выражения)

Статград вариант ИН2010201

Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 16 получим: 16=16∗1=8∗2=4∗416=16∗1=8∗2=4∗4, множество разностей содержит числа 15, 6 и 0. Найдите все натуральные числа, принадлежащие отрезку [1000000;2000000], у которых составленное описанным способом множество разностей будет содержать не меньше трёх элементов, не превышающих 100. В ответе перечислите найденные числа в порядке возрастания.

Ответ: 1113840; 1179360; 1208844; 1499400

Способ (без school)

Способ 2 (используя модуль school)

Статград вариант ИН2010301 (Решу ЕГЭ № 33527)

Найдите все натуральные числа, принадлежащие отрезку [101000000;102000000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания.

Ответ: 101075762; 101417282; 101588258; 101645282