Оптимизировать код

@pregret · Регистрация: 23.10.2018

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

Существует число N,не превосходящее 10^9.число можно разложить на множители N=B*C несколькими способами. Нужно найти и вывести минимально возможное значение суммы B+C. С клавиатуры вводится N. Выводится число, задающее минимально возможную сумму B+C. Я написал программу,но она не проходит по времени помогите оптимизировать код.Если же невозможно оптимизировать,прошу подсказать,как можно реализовать данный алгоритм.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n=int(input())
p=0
k=0
a=[]
b=[]
for i in range(1,n):
    if n%i==0:
        p=i
        k=n/i
        o=k+i
        b.append(o)
for item in b:
    a.append(int(item))
a=sorted(a)
print(a[0])

@grizlik78 · 24.10.2018, 08:44

Сильно данный алгоритм не заоптимизируешь. Хотя второй список тут выглядит абсолютно лишним, а чтобы числа получались сразу целыми деление стоило использовать целочисленное k = n // i.

Но. Во-первых, нет нужды делить на все числа от 1 до N, достаточно делить на число до корня из N, ибо дальше все числа N=B*C будут повторяться как N=C*B. Это очень сильно ускорит вычисления. Для наихудшего случая ускорение составит 4 порядка, то сеть более 10000 раз.
Ну и во-вторых, есть гипотеза, что минимальная сумма будет у сомножителей, которые ближе к корню из N.
Тогда программа принимает вид:

Python
1
2
3
4
5
6
from math import sqrt, ceil
n = int(input())
c = ceil(sqrt(n))
while n % c:
    c = c + 1
print(c + n // c)

@pregret · 24.10.2018, 14:52 **[ТС]**

С вами трудно не согласиться. Но тем не менее,код все таки не проходит по времени,поскольку алгоритм, по которому вы делали,впрочем как и я "идет в лоб",что не правильно.Возможно нужно создать список и туда засунуть множители,и найти такую пару B,C разница между которыми была бы наименьшей?

@grizlik78 · 24.10.2018, 15:18

Я почему-то подумал, что вверх идти так же недалеко, как и вниз, а это, разумеется, не так.

Попробуйте эту:

Python
1
2
3
4
5
6
from math import sqrt, floor
n = int(input())
c = floor(sqrt(n))
while с > 0 and n % c:
    c = c - 1
print(c + n // c)

Добавлено через 1 минуту
Ох, исправил условие чуток ещё.

@pregret · 24.10.2018, 15:28 **[ТС]**

Огромное спасибо,выручили.Только в условии цикла надо убрать c>0.

@grizlik78 · 24.10.2018, 15:33

Ну да, оно там, по сути, лишнее. Но на работоспособность и скорость влиять, вроде, не должно.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@pregret 0 / 0 / 0 Регистрация: 23.10.2018 Сообщений: 32
	24.10.2018, 14:52 [ТС]
	С вами трудно не согласиться. Но тем не менее,код все таки не проходит по времени,поскольку алгоритм, по которому вы делали,впрочем как и я "идет в лоб",что не правильно.Возможно нужно создать список и туда засунуть множители,и найти такую пару B,C разница между которыми была бы наименьшей? 0

@pregret 0 / 0 / 0 Регистрация: 23.10.2018 Сообщений: 32
	24.10.2018, 15:28 [ТС]
	Огромное спасибо,выручили.Только в условии цикла надо убрать c>0. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	24.10.2018, 15:33
	Ну да, оно там, по сути, лишнее. Но на работоспособность и скорость влиять, вроде, не должно. 0

Оптимизировать код

Решение