Не получается решить задачу с поиском делителей

Question

Найдите все натуральные числа, принадлежащие отрезку [1 000 000; 5 000 000], у которых ровно десять различных делителей, пять из которых четные и пять нечетные. В ответе перечислите найденные числа в порядке возрастания. Каждое число вводится в новое поле.

У меня получился такой код, но он долго выполняется и в итоге ничего не выдает

from sympy import divisors
from collections import Counter

def count_divisors(num):
    divs = divisors(num)
    div_counts = Counter(div % 2 for div in divs)
    return sum(div_counts[0] == 5 and div_counts[1] == 5 for num in range(1000000, 5000001))

valid_numbers = [num for num in range(1000000, 5000001) if count_divisors(num) == 1]
print(valid_numbers)

Answer 1

Цикл в операторе return лишний. Так будет работать, хотя и медленно:

from sympy import divisors
from collections import Counter


def count_divisors(num):
    divs = divisors(num)
    div_counts = Counter(div % 2 for div in divs)
    return div_counts[0] == 5 and div_counts[1] == 5


valid_numbers = [num for num in range(1000000, 5000001) if count_divisors(num)]
print(valid_numbers)

Две минуты:

$ time python temp.py
[1414562, 1847042, 3748322]

real  2m5.528s
user  2m5.456s
sys   0m0.020s

Проще и быстрее сосчитать делители напрямую:

n = 5000001
even = [0] * n
for i in range(2, n, 2):
    for j in range(i, n, i):
        even[j] += 1

odd = [0] * n
for i in range(1, n, 2):
    for j in range(i, n, i):
        odd[j] += 1

for i in range(1000000, n):
    if even[i] == odd[i] == 5:
        print(i)

Четырнадцать секунд:

$ time python temp.py
1414562
1847042
3748322

real  0m14.110s
user  0m13.948s
sys   0m0.012s

С другой стороны пять нечётных делителей имеют только числа вида 2^kp⁴, где p нечётное простое (подробности в статье Функция делителей на Википедии). Из них пять чётных делителей имеют числа вида 2p⁴. Такие числа перебрать можно очень быстро.

В программе ниже неэффективная простая проверка числа на простоту потому что проверять большие числа не нужно:

n = 5000000
for p in range(3, n + 1, 2):
    m = 2 * p ** 4
    if m > n:
        break
    if m >= 1000000 and all(p % i != 0 for i in range(3, p, 2)):
        print(m)

$ time python temp.py
1414562
1847042
3748322

real  0m0.044s
user  0m0.036s
sys   0m0.004s

БЛОГ НА HUSL

Не получается решить задачу с поиском делителей

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