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

Question

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

Рейтинг: 1Ответов: 1Опубликовано: 02.03.2023

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

как это работает с математической точки зрения?

python теория-чисел

Источник: Stack Overflow на русском

Answer 1

▲ 1

Если рассмотреть разложение n = p₁^e₁p₂^e₂p₃^e₃... (где p_i - различные простые), то можно догадаться что общее число делителей n равно (e₁ + 1)(e₂ + 1)(e₃ + 1).... В это число входят единица и само n, конечно.

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

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

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

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

m = 2
while True:
    n = m ** 4
    if 223456789 < n:
        break
    if 123456789 <= n:
        # is m prime?
        if all(m % i != 0 for i in range(2, m)):
            print(n, m ** 3)
    m += 1

$ time python nums.py
131079601 1225043
141158161 1295029
163047361 1442897

real  0m0.047s
user  0m0.032s
sys   0m0.012s