Найти наибольший нетривиальный делитель натурального числа
Формулировка. Дано натуральное число. Найти его наибольший нетривиальный делитель или вывести единицу, если такового нет.
Примечание 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. В цикле:
- Если n делится на i (то есть, остаток от деления числа n на i равен 0), то выводим i на экран и выходим из цикла с помощью break.
Код:
- program GreatestDiv;
- var
- i, n: word;
- begin
- readln(n);
- for i := n div 2 downto 1 do begin
- if n mod i = 0 then begin
- writeln(i);
- break
- end
- end
- end.
Кстати, у оператора ветвления if в цикле отсутствует else-блок. Такой условный оператор называется оператором ветвления с одной ветвью.
Нетривиальные делители числа
Здравствуйте, вот условие задачи:
Найдите числа, все нетривиальные делители которых образуют арифметическую прогрессию с шагом 12 на интервале [1200000; 1250000].
Для каждого найденного числа выведите само число и наименьший из нетривиальных делителей.
Все пары запишите в порядке возрастания найденных чисел одной строкой через пробел.
А это мой код для задачи:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
for i in range(1200000, 1250000+1): mas = [] k = 0 sch = 0 d = 2 maxd=0 if int(i**0.5) == i**0.5: while d * d i: if i%d == 0: k += 2 mas.append(i//d) d += 1 for j in range(len(mas)-1): if mas[j+1] - mas[j] == 12: sch+=1 if sch == len(mas): print(i, mas[0]) print(m)
Не понимаю, из-за чего код выдает ошибку, а так же как сделать так чтобы код правильно работал для данных условий?
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Зная простые делители числа и их количество, найти все делители числа
Добрый вечер. Есть задача: зная простые делители числа и их количество, найти все делители числа.
Даны натуральные числа p и q. Получить все делители числа q, взаимнопростые с p
как исправить, чтобы выводились только те делители, которые взаимнопросты с p? x=int(input(‘x=’)).
Делители числа
Поступает последовательность целых положительных чисел, 0 — конец последовательности. Определить.
Делители числа
Дано целое положительное число. Найдите все делители заданного числа. Вывести все делители данного.
Все делители числа
Напечатай все натуральные делители данного числа. Входные данные n — натуральное число Выходные.
7283 / 4105 / 1795
Регистрация: 27.03.2020
Сообщений: 6,929
Rumynoff,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
mas = [] for i in range(1200000, 1250000+1): sch = True d = 2 k = 1 mind=0 while d * d i: if i%d == 0: if mind == 0: k = 12 mind = d elif k == 12: sch = False break d += k if sch and mind: mas.extend([i, mind]) print(*mas)
Если через доказательство, что такие числа имеют всего(!) два нетривиальных делителя, то можно намного быстрее.
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Простые делители числа
Здравствуйте, помогите, пожалуйста, найти все простые делители от числа 4679000 до 5000000 Там.
Найти делители числа
Найти все делители числа n. (1 < n < 100 000 000 000) Вывести надо в списке в порядке.
Простые числа и делители
Дано натуральное число P. Вывести на экран все простые числа, не превосходящие P. Посчитать их.
Четные делители, нечетные делители, простые делители, составные делители, все делители
Помогите с задачей, не как не получается сделать. Создать HTML-документ p53.html, реализующий.
Нетривиальные числа
Доброго времени суток! Помогите найти ошибку в программе и заодно оптимизировать программу. Когда.
Или воспользуйтесь поиском по форуму:
Е25.3. имеющие ровно три нетривиальных делителя
имеющие ровно три нетривиальных делителя. Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.
Решение:
Найти наименьший нетривиальный делитель натурального числа
Формулировка. Дано натуральное число. Найти его наименьший нетривиальный делитель или вывести само это число, если такового нет.
Решение. Задача решается аналогично предыдущей. При этом необходимо начать обычный цикл с увеличением, при котором переменная цикла i изменяется от 2 до n (такая верхняя граница нужна для того, чтобы цикл всегда заканчивался, так как когда i будет равно n, выполнится условие n mod i = 0). Весь остальной код при этом не отличается.
Код:
- program SmallestDiv;
- var
- i, n: word;
- begin
- readln(n);
- for i := 2 to n do begin
- if n mod i = 0 then begin
- writeln(i);
- break
- end
- end
- end.