Как оптимизировать алгоритм?

@Fexx · Регистрация: 03.02.2021

Студворк — интернет-сервис помощи студентам

Я написал алгоритм для нахождения делителей числа.
Но вот хочется оптимизировать.
Он и так относительно оптимизирован,
я использовал факторизацию, вроде как в математике это так называется.
При факторизации если число делится то и делитель и остаток является делителем числа.

Вообщем как можно оптимизировать?

Вот код на Python:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def divs(n: int) -> list:
    a, b = 2.0, float(n)
    divisors = [1.0]
 
    while a < b:
        r = n / a
        if r.is_integer():  
            divisors += [a, b, r]
            b = r
 
        a += 1
 
    return set(divisors)
 
if __name__ == '__main__':
    print(divs(100))

@zeroalef · 03.02.2021, 23:35

Сообщение от Fexx

При факторизации если число делится то и делитель и остаток является делителем числа

Тяжело почитать вики? Факторизация -- разложение числа на простые множители. Например число 1023 = 3¹ * 11¹ * 31¹. В вашем случае надо уточнить цели задачи, т.к. для малых чисел и оптимизировать ничего не надо, а для больших чисел алгоритмы разные в зависимости от размеров числа. Так с первого взгляда можно сказать что:
1. не надо бегать по всем числам a += 1 , а только по простым a = next_prime(a);
2. арифметика должна быть целочисленной (это же теория чисел, что вы в самом деле);
3. проверяется остаток от деления, а не "целость" результата деления, и, если остаток равен нулю, то а остается прежним, но b = b / a
Если интересно, next_prime напишите самостоятельно и проверьте а учетом изменений

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def factorization(n):
    k, ret = 2, []
    
    while n != 1:
        if k > n:
            ret.append(k)
            break
        if n % k == 0:
            ret.append(k)
            n = n / k
            k = 2
        else:
            k += 1
    return ret
 
if __name__ == "__main__":
    print(factorization(105))
    print(factorization(1023))
    print(factorization(102345645654))
    """Здесь можно выйти покурить"""
    print(factorization(101248726349728398798730983764982734623))

Новые блоги и статьи Все статьи Все блоги /
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .