0

введите сюда описание изображения

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.

1 ответ 1

3

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

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 позволяет наблюдать как идёт наш процесс и видеть, сколько ещё осталось вычислений, где мы сейчас находимся, это удобно.
4
  • Спасибо за ответ, но это задание из ЕГЭ по информатике и в нем нельзя использовать нестандартные модули, т.е. tqdm.auto не установишь на экзамене. Добавил решение на Паскале, может что-то получится из него сделать. 26 мар 2021 в 7:19
  • @pointDeceit Решение на Паскале по сути соответствует моему решению, там все те же ходы использованы с квадратным корнем. tqdm можете просто выкинуть, он просто для красоты мной использован. defaultdict тоже можно не использовать, как делать тоже самое с обычным словарём написано в вашем коде на питоне. Хотя collections - это вообще стандартная библиотека. Да и tqdm тоже входит во множество пакетов с питоном.
    – CrazyElf
    26 мар 2021 в 7:23
  • В общем, я и так за вас готовое решение написал, а вообще-то по правилам этого сайта учебные задания тут не решают, учебные задания специально даются для того, чтобы вы учились. Возьмите на себя работу хотя бы отпилить от моего решения лишнее, это не сложно.
    – CrazyElf
    26 мар 2021 в 7:25
  • Спасибо, додедал, получилось. 26 мар 2021 в 7:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.