Нужно ускорить выполнение кода

Долго ли это работает? Я взял ваш код и стал менять в нём диапазон:

Видно что время меняется примерно пропорционально количеству чисел, которые надо проверить. Всего надо проверить пять миллионов. Сто тысяч проверяются за 14с. Ожидаемое время работы 50·14 = 700с. Двенадцать минут и готово. Не устраивает?

Идём дальше. Основной цикл печати странный: мы зачем-то ждём окончания всей работы, хотя можно было бы печатать найденные числа сразу. Так ждать легче:

for i in range(35000000,40000000+1):
    if d(i) != 0:
        print(i)

У большинства чисел делителей больше чем пять. А функция d накапливает их все, хотя могла бы остановиться значительно раньше. Надо позаботится чтобы в списке lst не было повторений. Если подумать, то делители вида i повторяться не могут. Делители вида n // i тоже. Они могут пересечься, если i == i // n. Проверим это:

def d(n):
    lst = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            if i % 2 != 0:
                lst.append(i)
            if (n // i != i) and ((n // i) % 2 != 0):
                lst.append(n // i)
            if len(lst) > 5:
                break
    if len(lst) == 5:
        return n
    return 0

С этим изменением сто тысяч чисел обработаются за 6.25с. То есть чуть больше пяти минут для всего диапазона.

Делители проверяются на чётность и это правильно. Но можно схитрить: уберём из n все двойки. То есть будем его делить пополам, пока делится. Нечётный остаток будет иметь только нечётные делители, можно сэкономить на проверках и сам цикл станет короче:

def d(n):
    while n % 2 == 0:
        n //= 2
    lst = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            lst.append(i)
            if n // i != i:
                lst.append(n // i)
            if len(lst) > 5:
                break
    if len(lst) == 5:
        return n
    return 0

С этим изменением сто тысяч чисел обработаются за 4.64с. Меньше четырёх минут для полного диапазона.

Раз число теперь всегда нечётное то у него не может быть чётных делителей. А мы их проверяем. В вызов range добавим шаг чтобы он перебирал только нечётные делители: range(1,int(n**0.5)+1,2).

С этим изменением сто тысяч чисел обработаются за 2.4с. То есть две минуты для всего диапазона. Эту программу я запустил и получилось чуть дольше, но не намного:

$ time py temp.py
35819648
38950081
39037448
39337984

real    2m12.187s
user    2m12.163s
sys 0m0.012s

P.S. Код можно ещё улучшать, но как его ускорить ещё больше я не придумал.

P.P.S. Если поменять алгоритм с простой проверки делителей на подход похитрее, можно решить задачу мгновенно. Но это уже за рамками вопроса "как ускорить мой код".

import os
import time

print("-" * 50 +'''\nНатуральные числа, принадлежащие отрезку [35000000;40000000], у которых ровно 5 различных нечётных делителей\n''' +"-" * 50)

# Засекаем время старта
v_start_time = time.time()

# Функция: проверка, является ли число простым (достаточно до sqrt)
def is_prime(v_n):
 if v_n < 2:
  return False
 for v_i in range(2, int(v_n ** 0.5) + 1):
  if v_n % v_i == 0:
   return False
 return True

# Список для хранения результатов
lst_results = []

# Перебираем все простые числа p, такие что p^4 * 2^k попадает в диапазон
for v_p in range(3, 1000, 2):  # 1000 — с запасом, т.к. 999^4 > 1e12
 if is_prime(v_p):
  v_p4 = v_p ** 4  # Вычисляем p^4

  v_n = v_p4
  while v_n <= 40_000_000:
   if v_n >= 35_000_000:
    # Получаем и сортируем нечётные делители (всегда 5 штук)
    lst_divs = [1, v_p, v_p**2, v_p**3, v_p**4]
    lst_results.append((v_n, lst_divs))
   v_n *= 2  # Умножаем на степень двойки

# Засекаем время окончания
v_end_time = time.time()

# Выводим время выполнения
print("Время выполнения: {:.6f} секунд".format(v_end_time - v_start_time))

# Выводим найденные числа и их нечётные делители
for v_n, lst_divs in sorted(lst_results):
 print(v_n, lst_divs)

os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

Результат:

Время выполнения: 0.000315 секунд
35819648 [1, 23, 529, 12167, 279841]
38950081 [1, 79, 6241, 493039, 38950081]
39037448 [1, 47, 2209, 103823, 4879681]
39337984 [1, 7, 49, 343, 2401]

UPDATE

Обновлённый бенчмарк. Дабы не загромождать ответ, код выложен здесь: https://pastebin.com/KjRWqMDT

Результаты:

# Testing with left=35_000_000, right=40_000_000
Solver          : 0.469784 seconds for 25930 iterations average: 0.018117ms
Fox             : 0.861001 seconds for 35772 iterations average: 0.024069ms
Volodarski2     : 1.127676 seconds for 118149 iterations        average: 0.009545ms
# Testing with left=35_000_000_000, right=40_000_000_000
Solver          : 0.763839 seconds for 6168 iterations  average: 0.123839ms
Fox             : 0.792939 seconds for 4877 iterations  average: 0.162587ms
Volodarski2     : 1.071768 seconds for 25692 iterations average: 0.041716ms
# Testing with left=35_000_000_000_000, right=40_000_000_000_000
Solver          : 0.846638 seconds for 1136 iterations  average: 0.745280ms
Fox             : 1.019128 seconds for 921 iterations   average: 1.106545ms
Volodarski2     : 0.834278 seconds for 3971 iterations  average: 0.210093ms
# Testing with left=35_000_000_000_000_000, right=40_000_000_000_000_000
Solver          : 1.018586 seconds for 212 iterations   average: 4.804652ms
Fox             : 1.005992 seconds for 107 iterations   average: 9.401796ms
Volodarski2     : 1.057230 seconds for 847 iterations   average: 1.248205ms
# Testing with left=35_000_000_000_000_000_000, right=40_000_000_000_000_000_000
Solver          : 0.905872 seconds for 19 iterations    average: 47.677492ms
Fox             : 0.432845 seconds for 5 iterations     average: 86.568975ms
Volodarski2     : 0.954767 seconds for 131 iterations   average: 7.288296ms
# Testing with left=35_000_000_000_000_000_000_000, right=40_000_000_000_000_000_000_000
Solver          : 0.585327 seconds for 2 iterations     average: 292.663455ms
Fox             : 0.929334 seconds for 1 iterations     average: 929.334402ms
Volodarski2     : 0.965677 seconds for 22 iterations    average: 43.894432ms
# Testing with left=35_000_000_000_000_000_000_000_000, right=40_000_000_000_000_000_000_000_000
Solver          : 1.803623 seconds for 1 iterations     average: 1803.623438ms
Fox             : 12.467032 seconds for 1 iterations    average: 12467.031717ms
Volodarski2     : 0.891086 seconds for 3 iterations     average: 297.028542ms

РЕШЕНИЕ С КЕШИРОВАНИЕМ СТЕПЕНЕЙ

Я тоже добавлю пять копеек.

Уже говорили, что число имеет ровно пять нечётных делителей, если оно представимо в виде 2^k * p^4, где p > 2 - простое число?

Вот на этом факте и построен решатель. Для ускорения счёта кэшируется всё, что можно:

• для простых чисел кешируются квадрат и четвертая степень
• для проверки, подходит ли простое число, используются логарифмы - они тоже кешируются.

"""
Найдите все натуральные числа, принадлежащие отрезку [35000000;40000000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.

Для решения задачи воспользуемся тем, что число имеет ровно 5 различных нечётных делителей, только если оно представимо в виде 2^k * p^4, где k - степень двойки, p - простое число.
"""
import math
import time
from typing import Any, Generator


class Number:
    """
    Число n вместе с кешированными значениями n^2 и n^4

    - n (number) - само число
    - _n2 (number) - n^2, используется для ускорения проверки на простоту 
    - _n4 (number) - n^4, используется для ускорения вычислений
    - _log2_n4 (number) - логарифм n^4 по основанию 2, используется для ускорения вычислений
    """

    def __init__(self, number: int):
        self.n = number
        self._n2 = number * number
        self._n4 = self._n2 * self._n2

        # В решателе используются логарифмы, поэтому кешируем их
        self._log2_n4 = math.log2(self._n4)

    def __repr__(self):
        return f"Number({self.n})"


class Result:
    """
    Результат вычислений.

    - prime (Number) - простое число.
    - degree (int) - степень двойки
    - value (int) - число вида 2^degree * prime^4
    """

    def __init__(self, prime: Number, degree: int):
        self.prime = prime
        self.degree = degree
        self.value = (1 << degree)*self.prime._n4

    def __repr__(self):
        return f"Result({self.prime}, {self.degree}, value={self.value})"


PRIMES_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
              41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


class Solver:
    """
    Решатель задачи. Находит все числа вида 2^k * p^4, где k - степень двойки, p - простое число в заданном диапазоне.


    - left (int) - левая граница диапазона (включительно)
    - right (int) - правая граница диапазона (включительно)
    """

    def __init__(self, left: int, right: int):
        self.left = min(left, right)
        self.right = max(left, right)
        if self.left < 2:
            raise ValueError("Left bound must be at least 2.")
        # В решателе используются логарифмы, поэтому кешируем их
        self._log2_left = math.log2(self.left)
        self._log2_right = math.log2(self.right)

        # Список простых чисел. Нужно обеспечить, что в нём есть все простые числа до \sqrt[4](right)
        # начинаем с простых чисел до 100
        self.primes = list(map(Number, PRIMES_100))
        # Добавляем простые числа до \sqrt[4](right)
        while self.primes[-1]._n4 < self.right:
            self.add_next_prime()

    def add_next_prime(self) -> Number:
        """
        Находит следующее простое число и добавляет его в список простых чисел.
        """
        p = self.primes[-1].n + 2
        while not self.is_prime(p):
            p += 2
        self.primes.append(Number(p))
        return self.primes[-1]

    def is_prime(self, n: int) -> bool:
        """
        Проверяет, является ли число простым.

        Более точно, проверяет, что среди self.primes нет делителей числа n.
        """
        assert (n >= 2)
        for prime in self.primes:
            if prime._n2 > n:
                break
            if n % prime.n == 0:
                return False
        return True

    def is_proper_num(self, p: Number) -> list[Result]:
        """
        Проверяет, является ли число p подходящим под условия задачи.

        Если число не подходит, возвращает пустой список.
        Если число подходит, возвращает список Result(p, k), где k - степень двойки, при которой 2^k * p^4 попадает в заданный диапазон.
        """
        if p._n4 > self.right:
            return []
        if p._n4 > self.left:
            return [Result(p, 0)]
        # Минимальная степень двойки, при которой 2^k * p^4 >= left
        deg = math.ceil(self._log2_left - p._log2_n4)
        # Максимальная степень двойки, при которой 2^k * p^4 <= right
        lim = math.floor(self._log2_right - p._log2_n4)

        if deg > lim:
            # В заданном диапазоне нет чисел вида 2^k * p^4
            return []
        return [Result(p, d) for d in range(deg, lim + 1)]

    def gen_proper_odd_primes(self) -> Generator[Result, None, None]:
        """
        Генератор, который перечисляет Result(p,k), то есть числа вида 2^k * p^4, где k - степень двойки, p - простое число, и 2^k * P^4 находится в заданном диапазоне.
        """
        for p in self.primes[1:]:
            yield from self.is_proper_num(p)
            # Если p^4 > right, то дальше нет смысла проверять
            if p._n4 > self.right:
                break

    def solve(self) -> list[Result]:
        """
        Решает задачу, находя все числа вида 2^k * p^4, где k - степень двойки, p - простое число в заданном диапазоне.

        Возвращает список объектов Result, соответствующих найденным простым числам.
        """
        return list(self.gen_proper_odd_primes())



if __name__ == "__main__":
    left = 35_000_000
    right = 40_000_000
    start_time = time.time()
    solver = Solver(left, right)
    results = solver.solve()
    end_time = time.time()
    print(f"Time taken: {end_time - start_time:.6f} seconds")

    for result in results:
        print(result)
    numbers = sorted([r.value for r in results])
    for n in numbers:
        print(n)

Вывод:

Time taken: 0.000195 seconds
Result(Number(7), 14, value=39337984)
Result(Number(23), 7, value=35819648)
Result(Number(47), 3, value=39037448)
Result(Number(79), 0, value=38950081)
35819648
38950081
39037448
39337984

Сравнение результатов

Небольшой бенчмарк

# Сравнение результатов

def fox(left, right):
    # Функция: проверка, является ли число простым (достаточно до sqrt)
    def is_prime(v_n):
        if v_n < 2:
            return False
        for v_i in range(2, int(v_n ** 0.5) + 1):
            if v_n % v_i == 0:
                return False
        return True

    # Список для хранения результатов
    lst_results = []

    # Перебираем все нечётные простые числа p, такие что p^4 * 2^k попадает в диапазон
    for v_p in range(3, 1000, 2):  # 1000 — с запасом, т.к. 999^4 > 1e12
        if is_prime(v_p):
            v_p4 = v_p ** 4  # Вычисляем p^4

            v_n = v_p4
            while v_n <= right:
                if v_n >= left:
                    # Получаем и сортируем нечётные делители (всегда 5 штук)
                    lst_divs = [1, v_p, v_p**2, v_p**3, v_p**4]
                    lst_results.append((v_n, lst_divs))
                v_n *= 2  # Умножаем на степень двойки
    return lst_results

def volodarski(left, right):

    def is_prime(n):
        return all(n % i != 0 for i in range(2, n))


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

    return list(numbers(left, right))

# benchmark
def benchmark(f, N = 1000):
    """
    Функция для бенчмарка функции f.
    """
    start_time = time.time()
    for _ in range(N):
        f()
    end_time = time.time()
    print(f"Time taken for {N} iterations: {end_time - start_time:.6f} seconds")
    dt = (end_time - start_time) / N
    print(f"Average time taken per iteration: {dt:.6f} seconds")


if __name__ == "__main__":
    N = 1000
    left = 35_000_000
    right = 40_000_000
    for i in [1, 10, 100, 1000]:
        left *= i
        right *= i
        print(f"# Testing with left={left}, right={right}")
        print("## Solver")
        benchmark(lambda: Solver(left, right).solve(), N)
        print("## Fox")
        benchmark(lambda: fox(left, right), N)
        print("## Volodarski")
        benchmark(lambda: volodarski(left, right), N if N < 1000 else 10)

# Testing with left=35000000, right=40000000
## Solver
Time taken for 1000 iterations: 0.073144 seconds
Average time taken per iteration: 0.000073 seconds
## Fox
Time taken for 1000 iterations: 1.035514 seconds
Average time taken per iteration: 0.001036 seconds
## Volodarski
Time taken for 10 iterations: 0.001307 seconds
Average time taken per iteration: 0.000131 seconds
# Testing with left=350000000, right=400000000
## Solver
Time taken for 1000 iterations: 0.058008 seconds
Average time taken per iteration: 0.000058 seconds
## Fox
Time taken for 1000 iterations: 0.505826 seconds
Average time taken per iteration: 0.000506 seconds
## Volodarski
Time taken for 10 iterations: 0.002486 seconds
Average time taken per iteration: 0.000249 seconds
# Testing with left=35000000000, right=40000000000
## Solver
Time taken for 1000 iterations: 0.248829 seconds
Average time taken per iteration: 0.000249 seconds
## Fox
Time taken for 1000 iterations: 0.624457 seconds
Average time taken per iteration: 0.000624 seconds
## Volodarski
Time taken for 10 iterations: 0.023346 seconds
Average time taken per iteration: 0.002335 seconds
# Testing with left=35000000000000, right=40000000000000
## Solver
Time taken for 1000 iterations: 1.705527 seconds
Average time taken per iteration: 0.001706 seconds
## Fox
Time taken for 1000 iterations: 0.723012 seconds
Average time taken per iteration: 0.000723 seconds
## Volodarski
Time taken for 10 iterations: 0.647147 seconds
Average time taken per iteration: 0.064715 seconds

def solve(left, right):
    primes_max = math.isqrt(math.isqrt(right)+1)+1
    
    primes = bytearray(primes_max)
    primes[0] = primes[1] = 1
    for i in range(math.isqrt(primes_max)+2):
        if primes[i]:
            continue
        
        primes[i*i::i] = [1]*len(range(i*i,primes_max,i))
    
    
    left_log2 = math.log2(left)
    right_log2 = math.log2(right)
    
    primes = enumerate(primes)
    next(primes); next(primes); next(primes)
    
    res = []
    for p, f in primes:
        if f: 
            continue

        value = p**4
        value_log2 = math.log2(value)
        
        deg = math.ceil(left_log2 - value_log2)
        lim = math.floor(right_log2 - value_log2)
        
        value <<= deg
        for i in range(deg, lim + 1):
            res.append(value)
            value <<= 1
    return sorted(res)

Данный код не особо сильно отличается от Volodarski2, но вроде показывает чуть более быстрый результат.