Как оптимизировать код из задачи ЕГЭ?

Question

[q1zin]

Есть задача из ЕГЭ, я решил её перебором, но выполняется больше 10 минут, это плохо. Единственное, что я придумал, это находить делители не от 1 до самого числа, а от 1 до числа в корне квадратном. Более не смог ничего придумать. Можете ли подсказать в какую сторону нужно копать? или же просто показать, как должно решаться такое)

def chet(a):
    d = set()
    for i in range(1,round(a**0.5)+1):
        if a % i == 0:
            if i % 2 != 0:
                d.add(i)
            if round(a/i) % 2 != 0:
                d.add(round(a/i))
    if len(d) >= 6: return d

    if len(d) == 5:
        print(d)

    return d

for i in range(105000000,115000000+1):
    d = chet(i)

    if len(d) == 5:
        print(i,max(d))

на данный момент лучшее решение:

def chet(a):
    d = set()
    for i in range(1,a+1):
        if a % i == 0 and i % 2 != 0:
            d.add(i)
    return d

a = 105000000
b = 115000000

for i in range(a,b+1):
    d = i
    while d % 2 == 0:
        d //= 2
    if d**0.25 == int(d**0.25):
        if len(chet(i)) == 5:
            print(i,d)

Ответ:
109401632 3418801
110766728 13845841
112550881 112550881
113592964 28398241

Comments

[Модератор]

Нарушение п.3.8 Регламента. Скриншоты фрагментов кода запрещены.
Фрагменты кода надо размещать в виде текста и оборачивать тэгом code для корректного отображения. Удобно делать кнопкой </>
Это обязательно, см.п.3.8 Регламента.
Сюда же относится traceback, ввод и вывод в консоли и другая структурированная текстовая инфа.

Answer 1

[slaver chief]

Если число любое разложить на простые множители и убрать из них двойки, количество нечетных делителей не изменится. Поэтому можно для начала делить четные числа на 2, пока они не станут нечетным.

Далее на этапе поиска делителей от 1 до корня числа можно не заморачиваться и на каждый делитель брать второй делитель, ибо если число n делится на a, то оно делится и на n/a. И прибавляешь к счетчику нечетных делителей 1 или 2, если один из них или оба нечетных. И после каждого увеличения счетчика проверять, больше ли счетчик 5 или нет, если да, то можно просто и не рассматривать число. А если их ровно 5, вписываешь в ответ. Будет быстрее.