Помогите оптимизировать алгоритм нахождения делителей

Question

def divider(number):
    pol = [1, number]
    number1 = number
    dividers = [2, 3, 5, 7]
    for i in range(2, number1 + 1):
        if number1 % i == 0:
            if pol.count(i) < 1:
                pol.append(i)
                number1 /= i
            else:
                pass
            for j in dividers:
                u = i * j
                if number % u == 0 and pol.count(u) < 1:
                    if i * j == number:
                        pass
                    else:
                        pol.append(u)
    print(sorted(pol))

Задумка в том, чтобы когда делитель был найден, программа делила на него число, тем самым, она работала бы быстрее. Но строчка number1 /= i только все портит, так как некоторая часть делителей просто не находится и также не изменяет значение nimber1 в цикле. Помогите пожалуйста(

Answer 1

Вот самый быстрый вариант

import math


def find_all_divisors(x):
       div_list = set()
       for y in range(1, math.floor(math.sqrt(x)) + 1):
           if x % y == 0:
               div_list.add(y)
               div_list.add(x // y)
       return [i for i in div_list]


print(find_all_divisors(40))

Answer 2

from functools import reduce


def sieve_of_eratosthenes(n): 
    is_prime = 2 * [False] + (n-1) * [True]
    p = 2
    while (p * p <= n): 
        if is_prime[p]: 
            for i in range(2 * p, n + 1, p): 
                is_prime[i] = False
        p += 1
    return is_prime


def all_prime_factors(n):
    is_prime = sieve_of_eratosthenes(n)
    prime_facts = [i for i in range(n + 1) if is_prime[i] and n % i == 0]
    prime_facts_powers = []
    for p in prime_facts:
        for i in range(1, n + 1):
            if n % p**i:
                break
        prime_facts_powers.append(i - 1)
    return prime_facts, prime_facts_powers, len(prime_facts)


def all_divisors(n):
    if n == 1:
        return [1]
    primes, powers, nfactors = all_prime_factors(n)
    exponents = nfactors * [0]
    divisors = []
    while True:
        factors = [primes[x] ** exponents[x] for x in range(nfactors)]
        divisor = reduce(lambda x, y: x * y, factors, 1)
        divisors.append(divisor)
        i = 0
        while True:
            exponents[i] += 1
            if exponents[i] <= powers[i]:
                break
            exponents[i] = 0
            i += 1
            if i >= nfactors:
                return divisors

Тест:

all_divisors(24)

[1, 2, 4, 8, 3, 6, 12, 24]

Объяснение:

Разложим число на простые множители и создаем все комбинации этих простых множителей.

Пример: Число 24.

Разложение: 24 = 2**3 * 3**1

Возможные степени 2: 2**0, 2**1, 2**2, 2**3
Возможные степени 3: 3**0, 3**1

Делители:
2**0 * 3**0 1
2**1 * 3**0 2
2**2 * 3**0 4
2**3 * 3**0 8
2**0 * 3**1 3
2**1 * 3**1 6
2**2 * 3**1 12
2**3 * 3**1 24

Answer 3

def find_all_div(n):
    div_n = []
    d = 1
    while d * d <= n:
        if n % d == 0:
            div_n.append(d)
            div_n.append(n // d)
        d += 1

    return div_n

Если использовать while, то можно обойтись без корня и округления в меньшую сторону. Должно работать ещё быстрее

Answer 4

import os
import math

print("-" * 70 + "\nНахождение делителей заданного натурального числа:\n" + "-" * 70)

number = 40
print(f"Делители числа {number}: {sorted(set(d for i in range(1, math.isqrt(number) + 1) if number % i == 0 for d in (i, number // i)))}")

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

БЛОГ НА HUSL

Помогите оптимизировать алгоритм нахождения делителей

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