Найти наибольший нетривиальный делитель натурального числа
Формулировка. Дано натуральное число. Найти его наибольший нетривиальный делитель или вывести единицу, если такового нет.
Примечание 1: делителем натурального числа a называется натуральное число b, на которое a делится без остатка. То есть выражение «b – делитель a» означает: a / b = k, причем k – натуральное число.
Примечание: нетривиальным делителем называется делитель, который отличен от 1 и от самого числа (так как на единицу и само на себя делится любое натуральное число).
Решение. Пусть ввод с клавиатуры осуществляется в переменную n. Попробуем решить задачу перебором чисел. Для этого возьмем число на единицу меньшее n и проверим, делится ли n на него. Если да, то выводим результат и выходим из цикла с помощью оператора break. Если нет, то снова уменьшаем число на 1 и продолжаем проверку. Если у числа нет нетривиальных делителей, то на каком-то шаге проверка дойдет до единицы, на которую число гарантированно поделится, после чего будет выдан соответствующий условию ответ.
Хотя, если говорить точнее, следовало бы начать проверку с числа, равного n div 2 (чтобы отбросить дробную часть при делении, если n нечетно), так как ни одно натуральное число не имеет делителей больших, чем половина это этого числа. В противном случае частное от деления должно быть натуральным числом между 1 и 2, которого просто не существует.
Данная задача также решается через for, но через другую его разновидность, и теперь счетчик будет убывать от n div 2 до 1. Для этого do заменится на downto, при позиции начального и конечного значений остаются теми же.
Алгоритм на естественном языке:
1) Ввод n;
2) Запуск цикла, при котором i изменяется от n div 2 до 1. В цикле:
Код:
Кстати, у оператора ветвления if в цикле отсутствует else-блок. Такой условный оператор называется оператором ветвления с одной ветвью.
Найти наибольший нетривиальный делитель натурального числа
Primary tabs
Forums:
Key Words for FKN + antitotal forum (CS VSU):
сверх нормы)
_____________
матфак вгу и остальная классика =)
ну так
прежде всего необходимо иное условие завершения перебора делителей, в данный момент вы решили задачу поиска 1-ого нетревиального делителя (а не последнего, который и нужен).
_____________
матфак вгу и остальная классика =)
На самом деле задача поиска
На самом деле задача поиска наименьшего нетривиального делителя не решена.
Если \$a не делится на 2, то тело цикла while не будет выполнено ни разу.
Произведение наименьшего нетривиального делителя числа \$a и наибольшего нетривиального делителя числа \$a равно числу \$a.
Можно исправить код, изменив условие цикла.
верно
_____________
матфак вгу и остальная классика =)
OK. Знаки доллара поставил.
OK. Знаки доллара поставил.
спасибо)
_____________
матфак вгу и остальная классика =)
счётчик цикла не изменяется
несогласованные условия. такой цикл никогда не закончится. почему?
_____________
матфак вгу и остальная классика =)
_____________
матфак вгу и остальная классика =)
увеличи вать значение :
и запуск цикла while при другом значении:
увеличи вать значение :
и запуск цикла while при другом значении:
_____________
матфак вгу и остальная классика =)
Интересно, что цикл while
Интересно, что цикл while здесь функционирует как условный оператор if.
_____________
матфак вгу и остальная классика =)
на самом деле решение вашей
_____________
матфак вгу и остальная классика =)
Кстати, из второй части
Кстати, из второй части приведённого решения можно сделать программу
для разложения натуральных чисел на простые множители.
Найти наибольший нетривиальный делитель числа
Даны три числа. Найти их наибольший общий делитель
8. Даны три числа. Найти их наибольший общий делитель.
Даны натуральные числа a и b. Найти их наибольший общий делитель
Даны натуральные числа a и b. Найти их наибольший общий делитель;
Найти наибольший общий делитель.
Даны два числа. Найти их наибольший общий делитель. Формат входных данных Вводятся два.
Найти наибольший общий делитель
даны натуральные числа a и b,найти их: а)наибольший общий делитель б)наименьшее общее кратное
Решение
Программирование для начинающих
Навигация
Главная страница
Задачи на Pascal
Об авторе
Задача № 14. Найти наибольший нетривиальный делитель натурального числа
Формулировка. Дано натуральное число. Найти его наибольший нетривиальный делитель или вывести единицу, если такового нет.
Примечание 1: делителем натурального числа a называется натуральное число b, на которое a делится без остатка. То есть выражение «b – делитель a» означает: a / b = k, причем k – натуральное число.
Примечание: нетривиальным делителем называется делитель, который отличен от 1 и от самого числа (так как на единицу и само на себя делится любое натуральное число).
Решение. Пусть ввод с клавиатуры осуществляется в переменную n. Попробуем решить задачу перебором чисел. Для этого возьмем число на единицу меньшее n и проверим, делится ли n на него. Если да, то выводим результат и выходим из цикла с помощью оператора break. Если нет, то снова уменьшаем число на 1 и продолжаем проверку. Если у числа нет нетривиальных делителей, то на каком-то шаге проверка дойдет до единицы, на которую число гарантированно поделится, после чего будет выдан соответствующий условию ответ.
Хотя, если говорить точнее, следовало бы начать проверку с числа, равного n div 2 (чтобы отбросить дробную часть при делении, если n нечетно), так как ни одно натуральное число не имеет делителей больших, чем половина это этого числа. В противном случае частное от деления должно быть натуральным числом между 1 и 2, которого просто не существует.
Данная задача также решается через for, но через другую его разновидность, и теперь счетчик будет убывать от n div 2 до 1. Для этого do заменится на downto, при позиции начального и конечного значений остаются теми же.
Алгоритм на естественном языке:
2) Запуск цикла, при котором i изменяется от n div 2 до 1. В цикле:
1. Если n делится на i (то есть, остаток от деления числа n на i равен 0), то выводим i на экран и выходим из цикла с помощью break.
Нетривиальный это что делитель
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.
Например, в диапазоне [5; 16] ровно три различных нетривиальных делителя имеет число 16, поэтому для этого диапазона вывод на экране должна содержать следующие значения:
Если решать задачу перебором — программа будет существенно неэффективна по времени. Заметим, что у каждого делителя числа имеется пара, например, пары делителей числа 16 будут выглядеть так: 1 и 16, 2 и 8, 4 и 4, всего пять различных делителей. Отсюда можно заключить, что имеет смысл перебирать возможные делители числа от единицы до корня от самого числа и, находя очередной делитель, прибавлять к переменной numDel 2. Также заметим, что поскольку число должно иметь три нетривиальных делителя, можно рассматривать только числа, квадратной корень из которых равен целому числу. Также отдельно будем учитывать квадратный корень числа, накапливая при этом в переменной numDel единицу.
Приведём решение на языке Pascal.
В результате работы программа должна вывести следующее:
Другой способ решения представлен в задаче 33104.
Решение задачи 25 из ЕГЭ по Информатике в PascalABC.NET
Нахождение делителей числа
При нахождении нетривиальных делителей натурального числа 𝑁 (которые отличны от 1 и самого числа 𝑁) часто предлагается перебирать числа из диапазона от 2 до [𝑁/2] (скобки [] обозначают операцию взятия целой части числа), поскольку на интервале от [𝑁/2]+1 до 𝑁−1 у числа 𝑁 нет делителей. При таком подходе для нахождения делителей, например 𝑁=10000 придется перебрать 4999 чисел (от 2 до 5000).
Перебор делителей числа 𝑁 можно оптимизировать, учитывая, что наименьший из пары делителей, таких что 𝑎∗𝑏=𝑁, не превышает квадратного корня из 𝑁; нужно только аккуратно обработать случай, когда число 𝑁 представляет собой квадрат целого числа. В этом случае для нахождения делителей, например 𝑁=10000 придется перебрать уже 99 делителей (от 2 до 100=sqrt(10000)).
Получается, что для определения количества делителей числа 𝑁 достаточно перебирать только числа от 2 до √N; если очередной делитель 𝑑 – это точный квадратный корень, добавляем в список делителей только один делитель, если нет – то добавляем пару делителей (𝑑, [𝑁/𝑑]). Потом (или сразу) необходимо добавить к списку делителей единицу и само число 𝑁.
PascalABC модуль school: список делителей числа
В PascalABC.Net для получения списка 𝐿𝑖𝑠𝑡, содержащего все натуральные делители числа 𝑛, включая 1 и 𝑛, могут быть использованы:
Задача
Вывести все делители натурального числа 𝑁.
Способ 1 (без school)
Способ 2 (используя модуль school)
Разложение числа в произведение простых множителей
Факторизацией натурального числа называется его разложение в произведение простых множителей. Причем такое разложение единственно.
PascalABC модуль school: разложение числа 𝑛 на простые множители
В PascalABC.Net для получения списка 𝐿𝑖𝑠𝑡, содержащего все простые делители числа 𝑛, могут быть использованы:
Задача
Разложить натуральное число 𝑁 в произведение простых множителей.
Рассмотрим реализацию решения задачи без использования функции 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑧𝑒(𝑛) модуля 𝑠𝑐ℎ𝑜𝑜𝑙, а затем с её использованием.
Способ 1 (без school)
Способ 2 (используя модуль school)
Другие полезные функции модуля school
PascalABC модуль school: простые числа
PascalABC модуль school: нахождение НОД и НОК пары чисел a и b
PascalABC модуль school: список цифр числа
Получение списка 𝐿𝑖𝑠𝑡, содержащего все цифры числа 𝑛 в порядке их следования слева направо:
Решение типовых задач ЕГЭ
Демо к ЕГЭ 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
Способ (без school)
Способ 2 (используя модуль school)
