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

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

  • автор:

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

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 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: 

как это работает с математической точки зрения?
Отслеживать
71.7k 5 5 золотых знаков 20 20 серебряных знаков 52 52 бронзовых знака
задан 1 мар 2023 в 22:34
Marilyn Manson Marilyn Manson
1 1 1 бронзовый знак
Возможный дубликат вопроса: Нахождение пяти нечётных делителей в промежутке чисел
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 

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

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

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

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

fgh's picture

задача плюсом отмечена в списке не была - но раз взялись, то решайте её. Это полезно.
Создайте отдельную заметку "нетривиальный делитель" в этом разделе (где и объясните что это такое и затем уже сошлитесь "отсюда туда")

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

  • Log in to post comments

vedro-compota's picture

Wed, 09/09/2015 - 11:02

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все .

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

Голосование за лучший ответ

Какие варианты могут быть? Три нетривиальных делителя могут быть или простыми числами, или два из них простых, а третье является их произведением. Остальное исключено! И меня не смущают числа в сотни миллионов, а скорее смущает, что таких чисел 203 с лишним миллиона! А если у каждого n из них нахождение простых делителей это задача сложности О (√n), то выбор нужной последовательности из всех из них представляется слишком затруднительной, если только не сформировать заранее список из простых чисел до ≈√728943762. Иначе за эту задачу не стоит и браться!

__ALPHA__Мастер (2008) 3 года назад
Делители должны быть: или три одинаковых простых числа, или два разных простых числа. Так вроде?
__ALPHA__Мастер (2008) 3 года назад

И мне кажется, тут лучше сформировать список простых чисел до 728943762 включительно, что бы в цикле от 525784203 до 728943762 сразу же исключать простые числа из проверки

__ALPHA__Мастер (2008) 3 года назад

Достал список простых чисел от 2 до 735632791. Каждое число с новой строки.
https://cloud .mail .ru/public/puJ2/B77f4BCDG (без двух пробелов)

__ALPHA__Мастер (2008) 3 года назад
Набросал пробный код, он будет считать примерно 4 года, надо как-то оптимизировать)
__ALPHA__Мастер (2008) 3 года назад
Немного оптимизировал. Теперь считает за 1 год)

Маша Малинина Просветленный (31972) __ALPHA__, ой, я кажется ошиблась 🙂 . Число 16 имеет три нетривиальных делителя: 2, 4 и 8, так что у меня в ответе количество возможных вариантов неверное. Ряд простых чисел в P=[2;≈√729млн) сформировать нетрудно. А дальше надо комбинировать из них произведения a³, a²·b, a·b·c на что-то там умноженные (может на самый младший делитель? 16=2⁴ - это ведь не куб !), ведь любое натуральное число раскладывается в произведение простых с их степенями кратности, но тут ещё надо всё продумать! Берём все такие простые из P, что a≤b≤с. Если их на что-то там умноженные произведения попадают в исходный отрезок, то и хорошо - учитываем этот факт! Вобщем получается комплексный цикл с двойным вложением и пока не вижу что ещё тут можно оптимизировать. Но эту задачу точно можно добить!

Маша МалининаПросветленный (31972) 3 года назад

Маша МалининаПросветленный (31972) 3 года назад

Пока что такой код. Считает за 1 год)

import time
import math

a = 525784203 #525 784 203
b = 728943762 #728 943 762

t = time.time()
print('Загружаем из файла в память список простых чисел от 2 до 735632791', end='; time=')
with open('d:/1/primes_to_735632791.txt') as f:
primes = f.read()
primes = list(map(int, primes.split()))
print(time.time() - t, 'сек')

t = time.time()
for k in range(a, b+1):
if k in primes: continue
sqrt = math.sqrt(k)
_k = k

i = 0 #номер простого числа на который пробуем делить без остатка
lst = [] #все простые делители числа k
while True:
if k%primes[i] == 0:
lst.append(primes[i])
k = k // primes[i]
else:
i += 1
if i > sqrt + 2: break

#Делители должны быть:
if len(lst) > 2 and lst[0] != lst[1]: break #..или два разных простых числа
if len(lst) > 3: break #..или три одинаковых простых числа,

if len(lst) == 2 and lst[0] != lst[1]: #два разных простых числа
print(f'k = ;', lst[0], lst[1], lst[0]*lst[1])
elif len(lst) == 3 and lst[0] == lst[1] == lst[2]: #три одинаковых простых числа
print(f'k = ;', lst[0], lst[0]**2, lst[0]**3)
#else:
# print(f'k = ; нетривиальных делителей больше трех')

if time.time() - t >= 60:
print('За минуту обработалось:', _k-a, 'из', b-a, f'осталось ~ часов' )
t = time.time()

__ALPHA__Мастер (2008) 3 года назад

Выводит все нетривиальные делители числа. Поменять код, что бы выводилось максимальное из них - элементарно.

for i in range(525784203,728943762+1):
sq=i**0.5
n=0
if int(sq)==sq:
md=1
for j in range(2,int(sq)-1):
if i%j==0:
if md==1: md=i//j
n+=2
if n==2: print(i,md)

607573201 3869893
705911761 4330747

p.s.
The program will process in 10 min

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

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