Требуется найти число в интервале [l;r] с максимальной суммой его натуральных делителей

@Kalighost · Регистрация: 26.02.2018

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

Требуется найти число в интервале [l;r] с максимальной суммой его натуральных делителей.
На вход программе даются два натуральных числа l и r (l≤r≤500), разделенные пробелом, — левая и правая граница интервала.
Требуется вывести одно натуральное число — ответ на задачу.

вводные данные:
50 100
выводные данные:
96

Буду признателен вам за помощь!

@Avaddon74 · 27.02.2018, 07:52

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
using namespace std;
 
int main() {
    int l, r, maxSum(0), sum(0), num(0);
    cin >> l >> r;
 
    for (; l < r; l++) {
        for (int i(1); i < l; i++) {
            if (l % i == 0) sum += i;
        }
        if (sum > maxSum) {
            maxSum = sum;
            num = l;
        }
        sum = 0;
    }
    if (num) cout << num << endl;
 
    return 0;
}

ValeryS · 27.02.2018, 08:01

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

i < l

само l считать или нет? вроде как тоже является делителем
тогда i <=l

@Avaddon74 · 27.02.2018, 08:06

Прошу прощения, упустил из виду:

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

l≤r≤500

тогда вот здесь for (; l < r; l++) нужно исправить на for (; l <= r; l++)

Добавлено через 3 минуты

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

само l считать или нет? вроде как тоже является делителем

По законам математики, если к сумме прибавлять само себе ещё раз, то это не повлияет на результат.
Допустим макс делителей у 10 но есть ещё и 8, если прибавлять к 10 + 10 = 20 и 8 + 8 = 16, десятка всё равно будет впереди

Добавлено через 55 секунд
Наверно запутанно объяснил

ValeryS · 27.02.2018, 08:10

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

По законам математики, если к сумме прибавлять само себе ещё раз, то это не повлияет на результат.

так тут то не само себя

например возьмем простые числа 2 3 5 7, если не брать делителям самого себя то сумма 1 1 1 1, а если брать то 3 4 6 8

@Avaddon74 · 27.02.2018, 09:01

ValeryS, ну вот число 8, делители 2 и 4 в сумме 6 и число 9 делители 3 если мы к 6 прибавим 8 получим 14, а к 3 прибавим 9 получим 12, все равно больше. если числа четные, то у них большая часть делителей одинаковые и мне кажется что всегда сумма делителей будет у четных больше

Добавлено через 45 минут
ValeryS, хотя я немного не прав, у 2 и 3 разница есть, но наверно это исключения
Надо подумать над математическим доказательством

@Kalighost · 27.02.2018, 09:24 **[ТС]**

Спасибо большое за помощь! Прога работает, единственное она не выводит ответ, если l и r равны. Я всунул ЖЕСТКИЙ костыль, за который самому стыдно)) Вот код, если кому-то понадобится!

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
#include "iostream"
#include "iomanip"
#include "cmath"
using namespace std;
 
int main() {
    int l = 0, r = 0, msum = 0, sum = 0, num = 0;
    cin >> l >> r;
 
    if (l != r){
    for (; l < r; l++) {
        for (int i = 1; i < l; i++) {
            if (l % i == 0) sum += i;
        }
        if (sum > msum) {
            msum = sum;
            num = l;
        }
        sum = 0;
    }
    if (num) cout << num << endl;
}
    else
        cout << l;
    return 0;
}

ValeryS · 27.02.2018, 09:48

Avaddon74, 18 и 41
без самого числа
18 1+2+3+6+9=21
41 1
итого 21>1 следовательно 18 максимальное
с самим числом
18 1+2+3+6+9+18=39
41 1+41 =42
здесь уже 41

Добавлено через 2 минуты

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

она не выводит ответ, если l и r равны.

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

for (; l < r; l++)

сделай вот так

C++
1
for (; l < =r; l++)

и будет тебе щастье

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

Я всунул ЖЕСТКИЙ костыль

это вот этот

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

if (l != r)

выбрось

@Avaddon74 · 27.02.2018, 11:35

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

Avaddon74, 18 и 41
без самого числа
18 1+2+3+6+9=21
41 1
итого 21>1 следовательно 18 максимальное
с самим числом
18 1+2+3+6+9+18=39
41 1+41 =42
здесь уже 41

Да, но ведь он проверит ещё и 40, а значит 40 будет больше, мы же говорим о последовательности чисел

Добавлено через 2 минуты
так то можно любое маленькое положительное взять и любое большое простое и получится тот же результат, но у нас изначально вопрос стоял: повлияет ли прибавление самого числа на результат, если перебирать соседние числа, а вот с соседними на результат не повлияет

ValeryS · 27.02.2018, 11:38

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

так то можно любое маленькое положительное взять и любое большое простое и получится тот же результат,

ну и ладно

@Avaddon74 · 27.02.2018, 12:17

ValeryS, Кстати, нашел нечетное число, у которого сумма делителей больше чем у соседнего четного это:
999998 - сумма делителей 1560672 (включая само число)
999999 - сумма делителей 2042880 (включая само число)
короче, числа типа 9...98 меньше чем 9..99
Я просто до этого считал, что любое четное будет иметь большую сумму делителей чем соседние нечетные, а оно эвоно как

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

Требуется найти число в интервале [l;r] с максимальной суммой его натуральных делителей

Решение

Решение

@Kalighost 1 / 1 / 1 Регистрация: 26.02.2018 Сообщений: 155

	Требуется найти число в интервале [l;r] с максимальной суммой его натуральных делителей 27.02.2018, 02:15. Показов 14267. Ответов 10 Метки нет (Все метки) Требуется найти число в интервале [l;r] с максимальной суммой его натуральных делителей. На вход программе даются два натуральных числа l и r (l≤r≤500), разделенные пробелом, — левая и правая граница интервала. Требуется вывести одно натуральное число — ответ на задачу. вводные данные: 50 100 выводные данные: 96 Буду признателен вам за помощь! 0

@Avaddon74 571 / 353 / 133 Регистрация: 15.09.2017 Сообщений: 1,239
	27.02.2018, 09:01
	ValeryS, ну вот число 8, делители 2 и 4 в сумме 6 и число 9 делители 3 если мы к 6 прибавим 8 получим 14, а к 3 прибавим 9 получим 12, все равно больше. если числа четные, то у них большая часть делителей одинаковые и мне кажется что всегда сумма делителей будет у четных больше Добавлено через 45 минут ValeryS, хотя я немного не прав, у 2 и 3 разница есть, но наверно это исключения Надо подумать над математическим доказательством 0

@Avaddon74 571 / 353 / 133 Регистрация: 15.09.2017 Сообщений: 1,239
	27.02.2018, 12:17
	ValeryS, Кстати, нашел нечетное число, у которого сумма делителей больше чем у соседнего четного это: 999998 - сумма делителей 1560672 (включая само число) 999999 - сумма делителей 2042880 (включая само число) короче, числа типа 9...98 меньше чем 9..99 Я просто до этого считал, что любое четное будет иметь большую сумму делителей чем соседние нечетные, а оно эвоно как 0