Нахождение трех четных делителя в промежутке

Question

Найдите все натуральные числа, принадлежащие отрезку [101 000 000; 102 000 000], у которых ровно 3 различных чётных делителей (количество нечётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания. Ответ:
101075762
101417282
101588258
101645282
Примерная задача (https://ru.stackoverflow.com/questions/1276027/Нахождение-пяти-нечётных-делителей-в-промежутке-чисел)

Мой код. Работает примерно за 3 минуты. Как его можно оптимизировать?

def tau(n):
    t =  0; sqrt = int(n**0.5)
    for d in range(1, sqrt):
        if n % d == 0:
            if d%2 == 0:
                t += 1
            if n//d%2 == 0:
                t += 1
            if t > 3:
                break
    if sqrt * sqrt == n:
        if sqrt%2 == 0:
        t += 1
    return t

for n in range(101000000, 102000000 + 1, 2):
    t = tau(n)
    if t == 3:
        print(n)

Примерная задача (https://ru.stackoverflow.com/questions/1276027/Нахождение-пяти-нечётных-делителей-в-промежутке-чисел). Я понял, как работать с нечетными делителями, но мне не понятно, как вывести формулу для четного делителя.

Answer 1

Немного подумав, дошел до решения )))

    def is_prime(n):
        for i in range(2, n):
            if n % i == 0:
                return False
        return True

    def numbers(m, n):
        i = 3
        while True:
            if is_prime(i):
                j = (i**2)*2
                if n < j:
                    break
                while j <= n:
                    if m <= j:
                        yield j
                    j = (j**2)* 2
            i += 2


    print(*sorted(numbers(101000000, 102000000)), sep='\n')

Answer 2

Задумаемся. Чтобы был хотя бы один простой четный делитель, нужно иметь делитель 2.

Если есть еще хотя бы два простых нечетных делителя p и q - имеем делители 2, 2p, 2q, 2pq - перебор!

Если есть один делитель p, но и p^2 тоже - имеем 2, 2p, 2p^2 - три делителя.

Если просто число имеет вид 2p - то делителей четных два.

Если двойка входит дважды - имеем 2 и 4 как делители, плюс 2p и 4p (если есть еще хоть один делитель p) - перебор.

Итак, числа должны быть вида 2*p^2.

Дальше понятно, как проверять быстро?

def is_prime(n):
    if n%2 == 0: return False
    i = 3
    while(i*i <= n):
        if n%i == 0: return False
        i = i+2
    return True

def lp(n):
    p = int((n//2)**0.5)
    if p%2 == 0: p = p + 1
    return p

def nums(m,n):
    p = lp(m)
    q = lp(n)
    while(p <= q):
        if is_prime(p): 
            print(2*p*p)
        p = p + 2

nums(101000000,102000000)

Результат расчета - тут: https://ideone.com/yqYOZ5

БЛОГ НА HUSL

Нахождение трех четных делителя в промежутке

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