Что такое нетривиальный делитель
Перейти к содержимому

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

  • автор:

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

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

maxi = 0 for i in range(123456789, 223456790): sqrti = i**0.5 numdel = 0 if round(sqrti) == sqrti: maxdel = 1 for j in range(2, round(sqrti) - 1): if i % j == 0: if maxdel == 1: maxdel = i // j numdel += 2 if numdel == 2: print(i, maxdel) 

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

if round(sqrti) == sqrti: 

как это работает с математической точки зрения?
Отслеживать
70.2k 5 5 золотых знаков 20 20 серебряных знаков 51 51 бронзовый знак
задан 1 мар 2023 в 22:34
Marilyn Manson Marilyn Manson
Возможный дубликат вопроса: Нахождение пяти нечётных делителей в промежутке чисел
2 мар 2023 в 5:18

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Если рассмотреть разложение n = p1 e1 p2 e2 p3 e3 . (где pi — различные простые), то можно догадаться что общее число делителей n равно (e1 + 1)(e2 + 1)(e3 + 1). . В это число входят единица и само n, конечно.

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

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

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

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

m = 2 while True: n = m ** 4 if 223456789 < n: break if 123456789  
$ time python nums.py 131079601 1225043 141158161 1295029 163047361 1442897 real 0m0.047s user 0m0.032s sys 0m0.012s 

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

Author24 — интернет-сервис помощи студентам

Здравствуйте, вот условие задачи:
Найдите числа, все нетривиальные делители которых образуют арифметическую прогрессию с шагом 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 - натуральное число Выходные.

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

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

Примечание 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.

Код:

  1. program GreatestDiv;
  2. var
  3. i, n: word;
  4. begin
  5. readln(n);
  6. for i := n div 2 downto 1 do begin
  7. if n mod i = 0 then begin
  8. writeln(i);
  9. break
  10. end
  11. end
  12. end.

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

Е25.3. имеющие ровно три нетривиальных делителя

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

Решение:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *