Задача на нахождение делителей на Python

Question

s = dict()
for i in range(289123456, 389123456):
    a = 0
    for j in range(2, i//2+1):
        if i % j == 0:
            if i not in s:
                s[i] = set()
            s[i].add(j)
            a += 1
    if a == 3:
        print(i, max(s[i]))

Программа работает с диапазоном [5; 16], но с большими числами вычисляется слишком долго. Как её оптимизировать?

Решение на Pascal:

var 
    numDel, i, j: longint;
    maxDel: longint;
    sqrtI: real;
begin
    for i := 289123456 to 389123456 do begin
        sqrtI := sqrt(i);
        numDel := 0;
        if (round(sqrtI) = sqrtI) then begin
            maxDel := 1;
            for j := 1 to round(sqrtI) do
                if (i mod j = 0) then begin
                    if (maxDel = 1) and (j <> 1) then maxDel := i div j;
                    if (j <> round(sqrtI)) then numDel := numDel + 2;
                    if (j * j = i) then numDel := numDel + 1;
                end;
            if numDel = 5 then writeln(i, ' ', maxDel);
        end;
    end;
end.

Answer 1

У меня получился такой код:

from math import sqrt
from collections import defaultdict
from tqdm.auto import tqdm as tq

s = defaultdict(set)
a = 289123456
b = 389123456
for i in tq(range(a, b + 1)):
    k = int(sqrt(i))
    if i != k * k:
        continue
    s[i].add(k)
    for j in range(2, k):
        if i % j == 0:
            s[i].add(j)
            s[i].add(i // j)
            if len(s[i]) > 3:
                break
    if len(s[i]) == 3:
        print(i, max(s[i]))

И такой результат я получил в Google Colab примерно за минуту:

294499921 2248091
352275361 2571353
373301041 2685619

Пояснения, хотя подобные задачи тут уже были, но эта вроде чуть другая:

Внутренний цикл нужно проходить до корня числа, потому что найдя любой делитель мы сразу находим ещё один делитель - число, делённое на этот найденный делитель. Когда мы пересечём корень числа, мы пойдём по тем делителям, которые могли таким образом уже найти ранее. Добавлять во множество соответственно нужно сразу оба найденных таким образом делителя.
Ровно три делителя (да и вообще любое нечётное число делителей) мы можем получить только в случае, если корень числа является его делителем. Во всех остальных случаях число делителей числа будет чётным (см. предыдущий шаг). Основное ускорение расчётов достигнуто именно с помощью этого умозаключения.
Если мы нашли больше делителей, чем нам нужно, цикл поиска можно прервать досрочно и не искать остальные делители.
defaultdict использовать несколько удобнее, чем dict, нужно меньше проверок делать в коде.
tqdm позволяет наблюдать как идёт наш процесс и видеть, сколько ещё осталось вычислений, где мы сейчас находимся, это удобно.

БЛОГ НА HUSL

Задача на нахождение делителей на Python

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