Что такое нетривиальный делитель

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

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.

_____________
матфак вгу и остальная классика =)

на самом деле решение вашей

_____________
матфак вгу и остальная классика =)

Кстати, из второй части

Кстати, из второй части приведённого решения можно сделать программу
для разложения натуральных чисел на простые множители.

Источник

Нетривиальные делители числа

Здравствуйте, вот условие задачи:
Найдите числа, все нетривиальные делители которых образуют арифметическую прогрессию с шагом 12 на интервале [1200000; 1250000].
Для каждого найденного числа выведите само число и наименьший из нетривиальных делителей.
Все пары запишите в порядке возрастания найденных чисел одной строкой через пробел.

А это мой код для задачи:

Зная простые делители числа и их количество, найти все делители числа
Добрый вечер. Есть задача: зная простые делители числа и их количество, найти все делители числа.

Даны натуральные числа p и q. Получить все делители числа q, взаимнопростые с p
как исправить, чтобы выводились только те делители, которые взаимнопросты с p? x=int(input(‘x=’)).

Делители числа
Поступает последовательность целых положительных чисел, 0 — конец последовательности. Определить.

Простые числа и делители
Дано натуральное число P. Вывести на экран все простые числа, не превосходящие P. Посчитать их.

Все простые делители числа
Здравствуйте, написал код для нахождения всех простых делителей числа, но он долго работает (я.

Источник

Задача № 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, при позиции начального и конечного значений остаются теми же.

Алгоритм на естественном языке:

1) Ввод n;

2) Запуск цикла, при котором i изменяется от n div 2до 1. В цикле:

1. Если n делится на i (то есть, остаток от деления числа n на i равен 0), то выводим i на экран и выходим из цикла с помощью break.

Кстати, у оператора ветвления if в цикле отсутствует else-блок. Такой условный оператор называется оператором ветвления с одной ветвью.

Источник

Что такое нетривиальный делитель

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

Например, в диапазоне [5; 16] ровно три различных натуральных делителя имеет число 16, поэтому для этого диапазона вывод на экране должна содержать следующие значения:

Если решать задачу перебором — программа будет существенно неэффективна по времени. Заметим, что у каждого делителя числа имеется пара, например, пары делителей числа 16 будут выглядеть так: 1 и 16, 2 и 8, 4 и 4, всего пять различных делителей. Отсюда можно заключить, что имеет смысл перебирать возможные делители числа от единицы до корня от самого числа и, находя очередной делитель, прибавлять к переменной numDel 2. Также заметим, что поскольку число должно иметь три нетривиальных делителя, можно рассматривать только числа, квадратной корень из которых равен целому числу. Также отдельно будем учитывать квадратный корень числа, накапливая при этом в переменной numDel единицу.

Приведём решение на языке Pascal.

numDel, i, j: longint;

for i := 289123456 to 389123456 do begin

if (round(sqrtI) = sqrtI) then begin

for j := 1 to round(sqrtI) do

if (i mod j = 0) then begin

if (maxDel = 1) and (j <> 1) then maxDel := i div j;

if (j <> round(sqrtI)) then numDel := numDel + 2;

if (j * j = i) then numDel := numDel + 1;

if numDel = 5 then writeln(i, ‘ ‘, maxDel);

В результате работы программа должна вывести следующее:

Приведём другое решение.

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

Источник

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

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

Примечание 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-блок. Такой условный оператор называется оператором ветвления с одной ветвью.

Источник