Нахождение пяти нечётных делителей в промежутке чисел
Задача:
Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Моё решение:
for number in range(35000000, 40000000+1):
divs = []
for div in range(1, round(number**0.5)+1, 2):
if number%div == 0:
divs.append(div)
if number**0.5 != int(number**0.5):
s = number // div
if s%2 ! =0:
divs.append(s)
if len(divs) == 5:
print(number)
Ответ к задаче должен быть таким:
35819648
38950081
39037448
39337984
Хотелось бы узнать почему мой код является не рабочим, ибо вместо этих четырёх чисел я получаю множество чисел, которые даже не доходят до первого числа из корректного ответа?
Ответы (5 шт):
Сначала приведу код, с которым мне удалось получить правильные ответы. Мне пришлось использовать numba.njit, потому что подсчёт идёт долго не смотря на некоторые оптимизации, которые я применил. Код выполняется порядка 2 минуты в Google Colab, а если не использовать numba, то обещает считать 50 минут, я не стал ждать проверять точное время.
from numba import njit
@njit()
def func():
for number in range(35000000, 40000000+1):
divs = []
for div in range(1, int(number**0.5)+1):
if div%2 and not number%div:
divs.append(div)
if len(divs) > 5:
break
nd = number//div
if nd%2 and nd == number/div and nd!=div:
divs.append(nd)
if len(divs) > 5:
break
if len(divs) == 5:
print(number, divs)
func()
Вывод:
35819648 [1, 23, 279841, 529, 12167]
38950081 [1, 38950081, 79, 493039, 6241]
39037448 [1, 4879681, 47, 103823, 2209]
39337984 [1, 7, 49, 343, 2401]
Теперь к сути. На самом деле вы не можете рассматривать только нечётные делители до корня из числа. Эта оптимизация хорошо работала для других подобных задач, но тут она не корректна. Ведь может получиться так, что у числа есть нечётный делитель больше корня из числа, которому соответствует чётный делитель меньший корня. А вы эти чётные делители не перебираете (шаг 2 у range) и поэтому вообще не увидите тот большой нечётный делитель!
Это не ответ на ваш вопрос, а другой подход к решению задачи. Можно проверять числа, разлагая их на делители, а можно конструировать подходящие числа из делителей.
Разложим искомое число на простые. Так как в дальнейшем нас будут интересовать нечётные делители, степень двойки выписана отдельно:
n = 2^k0 * p1^k1 * p2^k2 * ... * pi*ki,
где k0 - целое неотрицательное, k1, ..., ki - натуральные, p1, ..., pi - различные нечётные простые.
Любой делитель n конструируется как произведение простых из разложения выше. Сколько нечётных делителей мы можем сконструировать? (k1 + 1)(k2 + 1) ... (ki + 1). Это прозведение может быть равно пяти только если у числа ровно один нечётный простой делитель, который возводится в четвёртую степень.
Подробности можно посмотреть тут: функция делителей.
Искомое число должно иметь вид 2^k * p^4, где k - целое неотрицательное, p - нечетное простое. Сами нечётные делители тогда имеют вид 1, p, pp, ppp, pppp.
Будем искать такие числа в нужном диапазоне. Функция is_prime написана как можно проще, оценка показывает, что проверять числа больше 80 не нужно:
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
print(*sorted(numbers(35_000_000, 40_000_000)), sep='\n')
$ time python five_odd_divisors.py 35819648 38950081 39037448 39337984 real 0m0.021s user 0m0.020s sys 0m0.000s
Использован только базовый синтаксис:
def is_primenumber(n):
if n == 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
x = 35000000
y = 40000000
counter = 0
for j in range(3, int(y ** (1 / 4)) + 1):
if is_primenumber(j):
l = j ** 4
while l <= y:
if l >= x and l <= y:
print(l)
l *= 2
simple_numbers = []
for i in range(1,round(40000000**0.25)):
count = 0
for j in range(1,i):
if i%j == 0:
count+=1
if count == 1:
simple_numbers.append(i**4)
for i in range(35000000,40000001):
sm_nmbr = i
while sm_nmbr % 2 == 0:
sm_nmbr /= 2
if sm_nmbr in simple_numbers:
print(i)
Сначала находим все простые числа до корня 4 степени максимального числа для оптимизации счета (они в свою очередь нечетные) и все полученные числа возводим обратно в 4 степень и сохраняем в массив. Далее от каждого числа отсеиваем степени двойки, т.к это четные числа. И если получившееся число лежит в массиве, то оно подходит по условию. А условие таково, что n=(a1+1)(a2+1)(a3+1), где n кол-во делителей, a1 - степень числа 1,а так как любое число в 0 степени равно 1, подставляем 0, a2 - степень числа 2 и далее по порядку простых чисел. Т.к мы не учитываем двойки (a2+1) исключаем, a1 всегда будет равна 1, а вот a3 - это степень какого-то простого числа. То есть a3 будет равна 4 для выполнения условия (5 нечетных делителей). n = 1*(1+4) = 5 И методом подбора через цикл for выявляем подходящие числа.
Вывод
35819648
38950081
39037448
39337984
Я предпочитаю подробные, прокомментированные программы, разбитые на небольшие, обозримые кусочки, поэтому вот...
Здесь для ускорения счёта кешируется всё, что можно - простые числа, их степени, логарифмы.
"""
Найдите все натуральные числа, принадлежащие отрезку [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.000114 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