Необходимо найти все натуральные числа, принадлежащие отрезку [223344556; 323456789] и имеющие ровно три нетривиальных делителя

Question

На самом деле, рабочее решение на питоне есть, но его я не совсем понимаю. Формат вывода: для каждого числа нужно вывести само число и его наибольший нетривиальный делитель. Решение:


print(223344556**(1/4), 323456789**(1/4))
for i in range(123,135):
    ploho = True
    for j in range(2,i):
        if i % j == 0:
            ploho = False
            break
    if ploho:
        print(i**4, i**3)

Ответ:


260144641 2048383 
294499921 2248091

Я понимаю, почему у i^4 будет ровно 3 нетрив. делителя. Понимаю, почему i^3 - максимальный нетрив. делитель. Но разве не может быть такой ситуации, что в таком большом промежутке может быть число, которое имеет корень (число делителей нечётное), а также имеет ещё два нетрив. делителя?

Answer 1

Тривиальный делитель - это 1 или само число

В решение ищутся такие простые числа, чтобы p^4 = z, потому что тогда существует строго 3 нетривиальных делителя: p, p^2, p^3

предположим, что один из делителей числа z не простое число и не степень простого числа, т.е. Y=a*b, тогда z = X*Y=X*(a*b), где X - это еще какой-то делитель и делителей будет уже минимум 6: X, (a*b), a, b, (X*a), (X*b)

Т.е. возможные варианты по кол-ву нетривиальных делителей:

0 нетривиальных делителей, если z - простое число
1 нетривиальный делитель, если z = p^2 - квадрат простого числа
2 нетривиальных делителя, если z=p^3 - куб простого числа
2 нетривиальных делителя, если произведение двух простых чисел z=p1 * p2
3 нетривиальных делителя, если z=p^4 - 4 степень простого числа
4 нетривиальных делителя, если z=p^5 - 5 степень простого числа
4 нетривиальных делителя, если произведение квадрата простого числа на другое простое число z = p1 * p1 * p2

остальные варианты имеют большее число нетривиальных делителей -

например произведение трех простых чисел z = p1 * p2 * p3 даст уже 6 (!!!) нетривиальных делителей: p1, p2, p3, p1 * p2, p1 * p3, p2 * p3

а произведение простого числа на квадрат простого числа даст z = p1 * p1 * p2 даст 4 нетривиальных делителя: p1, p1 * p1, p2, p2 * p1

БЛОГ НА HUSL

Необходимо найти все натуральные числа, принадлежащие отрезку [223344556; 323456789] и имеющие ровно три нетривиальных делителя

Ответы (1 шт):