Найти число меньшее заданного числа n с максимальной суммой делителей.

@Fedor373 · Регистрация: 19.02.2018

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

Нужна помощь, нужно использовать циклы.
Дано натуральное n. Найти число меньшее n с максимальной суммой делителей.
Благодарю за помощь!

@Fixer_84 · 23.02.2018, 14:37

Fedor373, здравствуйте! Как вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
 
using namespace std;
 
int sumOfDevisors(int n)
{
    int sum = 0;
    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            if (n / i == i)
                sum += i;
            else
            {
                sum += i;
                sum += n / i;
            }
        }
    }
    return sum;
}
 
 
int main()
{
    int n, num, max = 0;
    cout << "Enter a number:\n";
    cout << "n = ";
    cin >> n;
    while (n--)
    {
        if (sumOfDevisors(n) > max)
        {
            max = sumOfDevisors(n);
            num = n;
        }
    }
    cout << "Found number: " << num << "\n";
    cout << "Maximum sum of devisors: " << max << "\n";
    system("pause");
    return 0;
}

P.S. Тут, конечно, следует сделать оценку, когда стоит остановиться, но я, к сожалению, не знаю как.

Байт · 23.02.2018, 16:17

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

следует сделать оценку, когда стоит остановиться, но я, к сожалению, не знаю как.

Очень грубая оценка

C++
1
if (n*(n+1) < 2*max) break;

@Fixer_84 · 23.02.2018, 17:58

...

@Fixer_84 · 24.02.2018, 19:19

Добавлено через 1 минуту
Байт, спасибо за оценку. Думаю, что даже такая оптимизация не будет лишней.

Байт · 24.02.2018, 19:28

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

даже такая оптимизация

Это я просто посчитал сумму всех чисел от 1 до n. Можно немного ее усилить, учитывая, что все числа от n/2 до n-1 не являются делителями.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@Fedor373 5 / 5 / 0 Регистрация: 19.02.2018 Сообщений: 76

	Найти число меньшее заданного числа n с максимальной суммой делителей. 20.02.2018, 06:24. Показов 1556. Ответов 5 Метки нет (Все метки) Нужна помощь, нужно использовать циклы. Дано натуральное n. Найти число меньшее n с максимальной суммой делителей. Благодарю за помощь! 0

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337
	23.02.2018, 17:58
	... 0

@Fixer_84 1505 / 969 / 812 Регистрация: 30.04.2016 Сообщений: 3,337
	24.02.2018, 19:19
	Добавлено через 1 минуту Байт, спасибо за оценку. Думаю, что даже такая оптимизация не будет лишней. 0