Найти дружественные числа, принадлежащие отрезку [1; 10000]

@OverClocker · Регистрация: 16.03.2010

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

Помогите, сегодня сдавать надо.

Дружественными числами являются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Например: 220 и 284 являются дружественными числами, поскольку сумма делителей числа 220 – это 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284, а сумма делителей числа 284 – это 1 + 2 + 4 + 71 + 142 = 220.
Найти дружественные числа, принадлежащие отрезку [1; 10000].

Заранее благодарен.

@SomniPhobia · 19.08.2019, 11:03

OverClocker, Romiusse, привет!
Вот мой вариант решения через 4 месяца после создания темы.

Кликните здесь для просмотра всего текста

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
#include <chrono>
#include <ratio>
 
//Выбор типа часов с самым точным периодом в рамках STL
using clock_type = std::chrono::high_resolution_clock;
//Выбор единиц измерения времени
using seconds = std::chrono::duration<double>;
using milliseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::milli>>;
using microseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::micro>>;
 
std::vector<size_t> split_to_divisors(size_t num);
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right);
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box);
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers);
 
int main()
{
    setlocale(LC_ALL, "Rus");
    const size_t left = 1u;
    const size_t right = 10000u;
 
    auto start = clock_type::now();
 
    std::vector<std::pair<size_t, size_t>> box = sum_of_divisors(left, right);
    std::vector<std::pair<size_t, size_t>> friendly_numbers = find_friendly_numbers(box);
    remove_duplicates_friendly_numbers(friendly_numbers);
    std::sort(std::begin(friendly_numbers), std::end(friendly_numbers));
 
    auto finish = clock_type::now();
    auto duration = milliseconds(finish - start);
    std::cout << "На поиск дружественных чисел в диапозоне от "
        << left  << " до " << right
        << " затрачено " << duration.count() << " миллисекунд" << std::endl;
 
    for (const auto& p : friendly_numbers)
        std::cout << p.first << " -> " << p.second << "\n";
 
    return 0;
}
 
std::vector<size_t> split_to_divisors(size_t num)
{
    std::vector<size_t> divisors(num);
    size_t idx0 = 0u;
    for (size_t idx = 1u; idx < num; ++idx)
        if (!(num % idx))
            divisors[idx0++] = idx;
    divisors.erase(std::next(std::begin(divisors), idx0), std::end(divisors));
    divisors.shrink_to_fit();
    return divisors;
}
 
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right)
{
    std::vector<std::pair<size_t, size_t>> box(right - left + 1u);
    size_t idx = 0u;
    for (size_t num = left; num <= right; ++num)
    {
        std::vector<size_t> divisors = split_to_divisors(num);
        size_t sum = std::accumulate(std::begin(divisors), std::end(divisors), 0u);
        box[idx++] = { num, sum };
    }
    return box;
}
 
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box)
{
    std::vector<std::pair<size_t, size_t>> friendly_numbers;
    for (const auto& p : box)
    {
        if (p.first != p.second)
        {
            auto predicate_find = [p](const std::pair<size_t, size_t>& p_now)
            {
                return p.first == p_now.second && p.second == p_now.first;
            };
            std::vector<std::pair<size_t, size_t>>::iterator it = std::find_if(std::begin(box), std::end(box), predicate_find);
            if (it != std::end(box))
                friendly_numbers.emplace_back((*it).first, (*it).second);
        }
    }
    return friendly_numbers;
}
 
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers)
{
    for (auto it = std::rbegin(friendly_numbers); it != std::rend(friendly_numbers); ++it)
    {
        auto p = *it;
        auto predicate_del = [p](const std::pair<size_t, size_t>& p_now)
        {
            return p.first == p_now.second && p.second == p_now.first;
        };
        std::vector<std::pair<size_t, size_t>>::iterator new_end_it =
            std::remove_if(std::begin(friendly_numbers), std::end(friendly_numbers), predicate_del);
        friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
    }
}

Скрин получен при запуске программы, сделанной в режиме релиза.
У меня несколько вопросов возникло:
1. При запуске программы в режиме дебага она падает. В ходе отладки, было обнаружено, что если закоментить строку 101

C++
1
friendly_numbers.erase(new_end_it, std::end(friendly_numbers));

то программа работает успешно. Это только в режиме дебага такое прослеживается. В режиме релиза программа завершается с кодом 0. В чём причина этого, как устранить ошибку?
2. В строке 51

C++
1
if (!(num % idx))

расположена медленная операция %. Может есть более быстрые аналоги по поиску остатка или определению кратности?

@SomniPhobia · 19.08.2019, 11:14

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

1. При запуске программы в режиме дебага она падает. В ходе отладки, было обнаружено, что если закоментить строку 101
friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
то программа работает успешно. Это только в режиме дебага такое прослеживается. В режиме релиза программа завершается с кодом 0. В чём причина этого, как устранить ошибку?

Ошибка была в том, что

C++
1
friendly_numbers.erase(new_end_it, std::end(friendly_numbers));

выполнялся в цикле.
Исправил.

Кликните здесь для просмотра всего текста

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
#include <chrono>
#include <ratio>
 
//Выбор типа часов с самым точным периодом в рамках STL
using clock_type = std::chrono::high_resolution_clock;
//Выбор единиц измерения времени
using seconds = std::chrono::duration<double>;
using milliseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::milli>>;
using microseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::micro>>;
 
std::vector<size_t> split_to_divisors(size_t num);
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right);
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box);
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers);
 
int main()
{
    setlocale(LC_ALL, "Rus");
    const size_t left = 1u;
    const size_t right = 10000u;
 
    auto start = clock_type::now();
 
    std::vector<std::pair<size_t, size_t>> box = sum_of_divisors(left, right);
    std::vector<std::pair<size_t, size_t>> friendly_numbers = find_friendly_numbers(box);
    remove_duplicates_friendly_numbers(friendly_numbers);
    std::sort(std::begin(friendly_numbers), std::end(friendly_numbers));
 
    auto finish = clock_type::now();
    auto duration = milliseconds(finish - start);
    std::cout << "На поиск дружественных чисел в диапозоне от "
        << left  << " до " << right
        << " затрачено " << duration.count() << " миллисекунд" << std::endl;
 
    for (const auto& p : friendly_numbers)
        std::cout << p.first << " -> " << p.second << "\n";
 
    return 0;
}
 
std::vector<size_t> split_to_divisors(size_t num)
{
    std::vector<size_t> divisors(num);
    size_t idx0 = 0u;
    for (size_t idx = 1u; idx < num; ++idx)
        if (!(num % idx))
            divisors[idx0++] = idx;
    divisors.erase(std::next(std::begin(divisors), idx0), std::end(divisors));
    divisors.shrink_to_fit();
    return divisors;
}
 
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right)
{
    std::vector<std::pair<size_t, size_t>> box(right - left + 1u);
    size_t idx = 0u;
    for (size_t num = left; num <= right; ++num)
    {
        std::vector<size_t> divisors = split_to_divisors(num);
        size_t sum = std::accumulate(std::begin(divisors), std::end(divisors), 0u);
        box[idx++] = { num, sum };
    }
    return box;
}
 
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box)
{
    std::vector<std::pair<size_t, size_t>> friendly_numbers;
    for (const auto& p : box)
    {
        if (p.first != p.second)
        {
            auto predicate_find = [p](const std::pair<size_t, size_t>& p_now)
            {
                return p.first == p_now.second && p.second == p_now.first;
            };
            std::vector<std::pair<size_t, size_t>>::iterator it = std::find_if(std::begin(box), std::end(box), predicate_find);
            if (it != std::end(box))
                friendly_numbers.emplace_back((*it).first, (*it).second);
        }
    }
    return friendly_numbers;
}
 
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers)
{
    std::vector<std::pair<size_t, size_t>>::iterator new_end_it = std::end(friendly_numbers);
    for (auto it = std::rbegin(friendly_numbers); it != std::rend(friendly_numbers); ++it)
    {
        auto p = *it;
        auto predicate_del = [p](const std::pair<size_t, size_t>& p_now)
        {
            return p.first == p_now.second && p.second == p_now.first;
        };
        new_end_it = std::remove_if(std::begin(friendly_numbers), new_end_it, predicate_del);
    }
    friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
}

silent_1991 · 19.08.2019, 11:20

SomniPhobia, падение у вас происходит потому, что вы модифицируете вектор friendly_numbers (а именно, удаляете из него элементы посредством вызова метода erase) в то время, пока итерируетесь по мену (цикл for, в теле которого вы удаляете элементы из вектора). По стандарту, после добавления/удаления элементов вектора все итераторы на него инвалидируются. Именно это в какой-то момент и происходит с итератором it, и на следующей итерации цикла при обращении к нему происходит ошибка сегментирования.

@SomniPhobia · 19.08.2019, 11:34

silent_1991, спасибо за ответ!
Я запустил поиск дружественных чисел на интервале [1; 130 000]. Одну пару моя программа не нашла. Мне интересно стало.
Может кто знает в чём причина и почему именно эта пара выпала.

silent_1991 · 19.08.2019, 11:42

В коде подробно разбираться лень, но есть предположение, что проблема в том, что второе число из не найденной пары больше 130000 (оно, как видно из списка, равно 139815).

@SomniPhobia · 19.08.2019, 12:23

silent_1991, спасибо! Да, я сейчас посмотрел, точно в этом причина.
Вот ещё скрины. Тут эта пара чисел (122 265 и 139 815) уже добавилась, а другой(их) нет, в которой(ых) одно из чисел превышает интервал поиска.

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .

@OverClocker 0 / 0 / 1 Регистрация: 16.03.2010 Сообщений: 17

	Найти дружественные числа, принадлежащие отрезку [1; 10000] 20.04.2011, 10:14. Показов 30232. Ответов 25 Метки нет (Все метки) Помогите, сегодня сдавать надо. Дружественными числами являются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Например: 220 и 284 являются дружественными числами, поскольку сумма делителей числа 220 – это 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284, а сумма делителей числа 284 – это 1 + 2 + 4 + 71 + 142 = 220. Найти дружественные числа, принадлежащие отрезку [1; 10000]. Заранее благодарен. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	19.08.2019, 11:20
	SomniPhobia, падение у вас происходит потому, что вы модифицируете вектор `friendly_numbers` (а именно, удаляете из него элементы посредством вызова метода `erase`) в то время, пока итерируетесь по мену (цикл `for`, в теле которого вы удаляете элементы из вектора). По стандарту, после добавления/удаления элементов вектора все итераторы на него инвалидируются. Именно это в какой-то момент и происходит с итератором `it`, и на следующей итерации цикла при обращении к нему происходит ошибка сегментирования. 1

@SomniPhobia 602 / 439 / 137 Регистрация: 22.11.2017 Сообщений: 1,407
	19.08.2019, 11:34
	silent_1991, спасибо за ответ! Я запустил поиск дружественных чисел на интервале [1; 130 000]. Одну пару моя программа не нашла. Мне интересно стало. Может кто знает в чём причина и почему именно эта пара выпала. Миниатюры 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	19.08.2019, 11:42
	В коде подробно разбираться лень, но есть предположение, что проблема в том, что второе число из не найденной пары больше 130000 (оно, как видно из списка, равно 139815). 1

@SomniPhobia 602 / 439 / 137 Регистрация: 22.11.2017 Сообщений: 1,407
	19.08.2019, 12:23
	silent_1991, спасибо! Да, я сейчас посмотрел, точно в этом причина. Вот ещё скрины. Тут эта пара чисел (122 265 и 139 815) уже добавилась, а другой(их) нет, в которой(ых) одно из чисел превышает интервал поиска. Миниатюры 0