Найти все пары натуральных дружественных чисел, меньших 50000.

@sisi11 · Регистрация: 09.02.2018

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

Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого (само другое число в качестве делителя не рассматривается). Найти все пары натуральных дружественных чисел, меньших 50000.

@renat_dmitriev · 21.09.2018, 15:10

В чем именно затруднение? Если в алгоритме, то есть специальный раздел форума по алгоритмам.

@klopp · 22.09.2018, 15:40

JavaScript
1
2
3
4
5
6
7
8
const getFriendlyNumbers = (max) => {
    const getSumDivis = (num) => new Array(parseInt(num / 2)).fill(0).reduce((sum, el, i) => sum += !(num % (i + 1)) ? i + 1 : 0, 0);  
    let res = [];
    let arr = new Array(max).fill(0).map((el, i) => getSumDivis(i));
    arr.forEach((el, i) => {if(i == arr[arr[i]] && arr[i] != i) res.push([i, arr[i]]);});
    return res.filter((el, i) => !(i & 1));
}
console.log(getFriendlyNumbers(50000));

@renat_dmitriev · 23.09.2018, 00:06

klopp, Во-первых у вас судя по всему в делители включена единица, что наверное все-таки неверно, хотя я не уверен, во вторых ваш перебор в лоб даже на скромных 50000 работает 10 секунд, на 100000 система может просто лечь.

Добавлено через 4 часа 24 минуты
Оптимизированный по скорости вариант, 50000 находит моментально, за приемлемое время(10 секунд) находит пары для 10 миллионов.

JavaScript
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
function friends(max) {
    
    var res = []
    var allNumbers = {'1': 0};
    var allNumbersTiny = null, limit = 100, tinyLimit = 0; //Для оптимизации поиска
 
    var numbers = allNumbers;
 
    for(simple = 2; simple <= max / 2; simple++) {
 
        if(simple in allNumbers) continue;
 
        if(simple >= limit) {
 
            // После 100 создаем мини-массив, поскольку цикл по ключам объекта
            // работает слишком долго, а нам чем дальше, тем более маленькие числа
            // будут нужны для перебора
 
            var tinyLimitNew = Math.floor((max + 100) / simple);
            if(!allNumbersTiny) {
                allNumbersTiny = {};
                for(var i = 1; i <= tinyLimitNew; i++) allNumbersTiny[i] = allNumbers[i];
 
                numbers = allNumbersTiny;
            } else {
                for(var i = tinyLimitNew + 1; i <= tinyLimit; i++) delete allNumbersTiny[i];
            }
 
            tinyLimit = tinyLimitNew;
            limit += 100;
        }
 
        for(k in numbers) {
 
            var product = k * simple;
            if(product > max) break;
 
            var prevSum = numbers[k], currSum = prevSum, prevProduct = +k;
            var currPow = simple;
 
            while(product <= max) {
 
                if(k == 1) {
                    currSum += currPow === simple ? 0 : prevProduct;
                }  else {
                    currSum += prevProduct + currPow + currPow * prevSum;
                }
                prevProduct = product;
 
                allNumbers[product] = currSum;
                if(allNumbers[currSum] === product) res.push([product, currSum]);
 
                if(product <= tinyLimit) allNumbersTiny[product] = currSum;
 
                currPow *= simple;
                product *= simple;
            }
        }
    }
 
    console.log(res);
}
 
friends(50000);

@klopp · 23.09.2018, 12:36

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

в делители включена единица

Да, ибо, судя по результатам Пифагора и более поздних авторов, единица входит в сумму делителей
Ваш код очень быстрый, но результаты неверные, вы их проверяли?
Ваши:
0: (2) [75, 48]
1: (2) [1925, 1050]
2: (2) [195, 140]
3: (2) [2024, 2295]
4: (2) [20735, 9504]
5: (2) [16587, 8892]
6: (2) [1648, 1575]
7: (2) [6128, 5775]
Должно быть:
0: (2) [220, 284]
1: (2) [1184, 1210]
2: (2) [2620, 2924]
3: (2) [5020, 5564]
4: (2) [6232, 6368]
5: (2) [10744, 10856]
6: (2) [12285, 14595]
7: (2) [17296, 18416]
М.б. это из-за той самой единицы.
Чуть медленнее вашего(210ms vs 178ms):

JavaScript
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
const getFriendlyNumbers = (max) => {
    if(isNaN(max)) return null;
    const getSumDivis = (num) => {
        if(num < 4) return 1;
        let sum = [];
        for(let i = 2, N = Math.sqrt(num); i <= N; i++){
            let tmp = num / i;
            if(tmp == (tmp ^ 0)){
                if(!sum.includes(i)){
                    sum.push(tmp);
                    sum.push(i);
                }
            }   
        }
        return sum.reduce((p,el) => p += el, 1) ;
    }
    let res = [], arr = [];
    for(let i = 0; i <= max; i++)
        arr[i] = getSumDivis(i);
    for(let i = 0; i < arr.length; i++){
        if(i == arr[arr[i]] && i != arr[i])
            res.push([i, arr[i]]);
    }
    return res.filter((el, i) => !(i & 1));
}
console.log(getFriendlyNumbers(50000));

а вот на миллионе разница уже ощутимая 11сек против 1.5сек

@renat_dmitriev · 23.09.2018, 15:03

klopp, Да, это из-за единицы, сделал опционально, по умолчанию включая единицу

JavaScript
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
function summands(max, include1 = true) {
 
    var res = []
    var allNumbers = {'1': +include1};
    var allNumbersTiny = null, limit = 100, tinyLimit = 0; //Для оптимизации поиска
 
    var numbers = allNumbers;
 
    for(simple = 2; simple <= max / 2; simple++) {
 
        if(simple in allNumbers) continue;
 
        if(simple >= limit) {
 
            // После 100 создаем мини-массив, поскольку цикл по ключам объекта
            // работает слишком долго, а нам чем дальше, тем более маленькие числа
            // будут нужны для перебора
 
            var tinyLimitNew = Math.floor((max + 100) / simple);
            if(!allNumbersTiny) {
                allNumbersTiny = {};
                for(var i = 1; i <= tinyLimitNew; i++) allNumbersTiny[i] = allNumbers[i];
 
                numbers = allNumbersTiny;
            } else {
                for(var i = tinyLimitNew + 1; i <= tinyLimit; i++) delete allNumbersTiny[i];
            }
 
            tinyLimit = tinyLimitNew;
            limit += 100;
        }
 
        for(k in numbers) {
 
            var product = k * simple;
            if(product > max) break;
 
            var prevSum = numbers[k] - include1, currSum = prevSum, prevProduct = +k;
            var currPow = simple, sum;
 
            while(product <= max) {
 
                if(k == 1) {
                    currSum += currPow === simple ? 0 : prevProduct;
                }  else {
                    currSum += prevProduct + currPow + currPow * prevSum;
                }
                prevProduct = product;
                
                sum = currSum + +include1;
 
                allNumbers[product] = sum;
                if(sum !== product && allNumbers[sum] === product) res.push([product, sum]);
 
                if(product <= tinyLimit) allNumbersTiny[product] = sum;
 
                currPow *= simple;
                product *= simple;
            }
        }
    }
 
    console.log(res);
}
 
summands(500);

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

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

а вот на миллионе разница уже ощутимая 11сек против 1.5сек

Это происходит оттого, что хоть вы и оптимизировали поиск множителей для каждого конкретного числа, но зависимость все еще геометрическая. Мой алгоритм не ищет делители для каждого числа, а идет с обратной стороны - он берет последовательно простые числа и составляет из них прочие, перемножая все степени простого числа на все числа, рассчитанные ранее и по несложной формуле получая сумму делителей. Поэтому с увеличением max зависимость арифметическая.

Единственная проблема была, что строчка for(k in numbers) , которая для каждого просто числа перебирает рассчитанные ранее числа, при большом количестве элементов работает очень долго, даже если после первой итерации будет break, на десятках тысяч записей инициализация итерируемого массива занимает несколько миллисекунд, поэтому пришлось добавить код, создающий уменьшенную копию основного хэша чисел, где будет сначала 500 элементов, и который будет постепенно уменьшаться, так как понятно что при max = 50000 простые числа больше 100 могут быть умножены только на числа меньшие 500.

Фактически весь этот алгоритм - наверное почти что образец поиска делителей для большого диапазона чисел, непосредственно к задаче относится только строчка

JavaScript
1
if(sum !== product && allNumbers[sum] === product) res.push([product, sum]);

@outoftime · 25.09.2018, 04:42

sisi11, klopp, renat_dmitriev, дорогие братья и сёстры, обратите внимание на качество написанного вами кода. Все мы знаем что оптимизация - дело хорошее, но дело вот в чём: оптимизировать можно вечность, ибо нету ничего совершенного помимо идеи. Только идея о вещи может быть совершенной, но никак не сама вещь.

Заканчиваю философствовать. Есть
$ node --version
v9.11.1
на нём будем тестировать код на скорость следующим образом

run.js

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
const klopp = require('./klopp').test;
const renat = require('./renat').test;
const tftm  = require('./tftm').test;
 
timeIt(klopp, 50000, 'klopp');
timeIt(renat, 50000, 'renat');
timeIt(tftm,  50000, 'tftm');
 
function timeIt(test, n, name) {
    console.time(name);
    console.log(test(n));
    console.timeEnd(name);
}

Код уважаемых klopp и renat_dmitriev будем экспортировать в виде функции test и поместим их в файлы klopp.js и renat.js соответственно.

klopp.js

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

JavaScript
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
const getFriendlyNumbers = (max) => {
    if(isNaN(max)) return null;
    const getSumDivis = (num) => {
        if(num < 4) return 1;
        let sum = [];
        for(let i = 2, N = Math.sqrt(num); i <= N; i++){
            let tmp = num / i;
            if(tmp == (tmp ^ 0)){
                if(!sum.includes(i)){
                    sum.push(tmp);
                    sum.push(i);
                }
            }   
        }
        return sum.reduce((p,el) => p += el, 1) ;
    }
    let res = [], arr = [];
    for(let i = 0; i <= max; i++)
        arr[i] = getSumDivis(i);
    for(let i = 0; i < arr.length; i++){
        if(i == arr[arr[i]] && i != arr[i])
            res.push([i, arr[i]]);
    }
    return res.filter((el, i) => !(i & 1));
}
 
exports.test = getFriendlyNumbers;

renat.js

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

JavaScript
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
function summands(max, include1 = true) {
 
    var res = []
    var allNumbers = {'1': +include1};
    var allNumbersTiny = null, limit = 100, tinyLimit = 0; //Для оптимизации поиска
 
    var numbers = allNumbers;
 
    for(simple = 2; simple <= max / 2; simple++) {
 
        if(simple in allNumbers) continue;
 
        if(simple >= limit) {
 
            // После 100 создаем мини-массив, поскольку цикл по ключам объекта
            // работает слишком долго, а нам чем дальше, тем более маленькие числа
            // будут нужны для перебора
 
            var tinyLimitNew = Math.floor((max + 100) / simple);
            if(!allNumbersTiny) {
                allNumbersTiny = {};
                for(var i = 1; i <= tinyLimitNew; i++) allNumbersTiny[i] = allNumbers[i];
 
                numbers = allNumbersTiny;
            } else {
                for(var i = tinyLimitNew + 1; i <= tinyLimit; i++) delete allNumbersTiny[i];
            }
 
            tinyLimit = tinyLimitNew;
            limit += 100;
        }
 
        for(k in numbers) {
 
            var product = k * simple;
            if(product > max) break;
 
            var prevSum = numbers[k] - include1, currSum = prevSum, prevProduct = +k;
            var currPow = simple, sum;
 
            while(product <= max) {
 
                if(k == 1) {
                    currSum += currPow === simple ? 0 : prevProduct;
                }  else {
                    currSum += prevProduct + currPow + currPow * prevSum;
                }
                prevProduct = product;
                
                sum = currSum + +include1;
 
                allNumbers[product] = sum;
                if(sum !== product && allNumbers[sum] === product) res.push([product, sum]);
 
                if(product <= tinyLimit) allNumbersTiny[product] = sum;
 
                currPow *= simple;
                product *= simple;
            }
        }
    }
 
    for (let i in res)
        res[i].sort();
 
    res.sort(function(x, y) { return x[0] > y[0] });
 
    return res;
}
 
exports.test = summands;

Да, ещё добавим свою поделку, пусть это будет tftm.js

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

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function sumOfFactors(a) {
    let res = 0, factor = 2;
    for (; factor*factor < a; ++factor)
        if (a % factor == 0)
            res += factor + a/factor;
    if (factor*factor == a)
        res += factor;
    return res + 1;
}
 
function test(n) {
    let res = [];
    for (let i = 1; i <= n; ++i) {
        let j = sumOfFactors(i);
        if (i < j && sumOfFactors(j) == i)
            res.push([i, j]);
    }
    return res;
}
 
exports.test = test;

И запустим уже наше тестирование скорости:

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

Code
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
$ node run.js 
[ [ 220, 284 ],
  [ 1184, 1210 ],
  [ 2620, 2924 ],
  [ 5020, 5564 ],
  [ 6232, 6368 ],
  [ 10744, 10856 ],
  [ 12285, 14595 ],
  [ 17296, 18416 ] ]
klopp: 219.153ms
[ [ 220, 284 ],
  [ 1184, 1210 ],
  [ 2620, 2924 ],
  [ 5020, 5564 ],
  [ 6232, 6368 ],
  [ 10744, 10856 ],
  [ 12285, 14595 ],
  [ 17296, 18416 ] ]
renat: 112.746ms
[ [ 220, 284 ],
  [ 1184, 1210 ],
  [ 2620, 2924 ],
  [ 5020, 5564 ],
  [ 6232, 6368 ],
  [ 10744, 10856 ],
  [ 12285, 14595 ],
  [ 17296, 18416 ] ]
tftm: 247.590ms

И тут вы можете сказать мол "Да у Рената скорость в 2.5 раза выше, зачем ты вообще код писал?" Отвечать я на этот вопрос не собираюсь, просто попрошу вас разобраться и понять как работают все 3 тестируемые функции из файлов приведённых выше. Советую начинать с лёгкого и переходить к более сложному, для этого вот небольшая подсказка в виде размера файлов в байтах:

$ ls -lh klopp.js renat.js tftm.js
<useless> 789 <useless> klopp.js
<useless> 2223 <useless> renat.js
<useless> 411 <useless> tftm.js

Можете для себя сделать оценку, на сколько сложно для вас было понять как и почему работает тот или иной способ решения.

@renat_dmitriev · 25.09.2018, 11:07

outoftime, Если мы ограничиваемся 50000, то вы абсолютно правы. Разница в 100 миллисекунд абсолютно несущественна и простота кода приоритетна. Но как я описывал выше, подобный подход перебора чисел и нахождения их множителей дает геометрическую прогрессию при увеличении числа. Мой же алгоритм перемножения простых чисел дает арифметическую прогрессию, поскольку для нахождения суммы множителей для чисел 100 и 1000000 делается одинаковое количество операций. Поэтому как гласит народная мудрость нет смысла сравнивать ж-пу с пальцем, ж-пу надо сравнивать с ж-пой, а палец с пальцем.

@outoftime · 25.09.2018, 22:13

renat_dmitriev, Вы когда за хлебом идёте всё время частный самолёт нанимаете?

@renat_dmitriev · 25.09.2018, 22:53

outoftime,

Не по теме:

Дайте пожалуйста ссылку на мой комментарий, где я просил вас читать мне лекции и нотации. Если такого комментария не существует, то давайте пожалуйста будет чуть более уважительны друг к другу и избавим форум от бессмысленного флуда.

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

@sisi11 2 / 2 / 0 Регистрация: 09.02.2018 Сообщений: 140

	Найти все пары натуральных дружественных чисел, меньших 50000. 21.09.2018, 12:13. Показов 7304. Ответов 9 Метки нет (Все метки) Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого (само другое число в качестве делителя не рассматривается). Найти все пары натуральных дружественных чисел, меньших 50000. 0

@renat_dmitriev 392 / 294 / 121 Регистрация: 26.08.2016 Сообщений: 902
	21.09.2018, 15:10
	В чем именно затруднение? Если в алгоритме, то есть специальный раздел форума по алгоритмам. 0

@renat_dmitriev 392 / 294 / 121 Регистрация: 26.08.2016 Сообщений: 902
	25.09.2018, 11:07
	outoftime, Если мы ограничиваемся 50000, то вы абсолютно правы. Разница в 100 миллисекунд абсолютно несущественна и простота кода приоритетна. Но как я описывал выше, подобный подход перебора чисел и нахождения их множителей дает геометрическую прогрессию при увеличении числа. Мой же алгоритм перемножения простых чисел дает арифметическую прогрессию, поскольку для нахождения суммы множителей для чисел 100 и 1000000 делается одинаковое количество операций. Поэтому как гласит народная мудрость нет смысла сравнивать ж-пу с пальцем, ж-пу надо сравнивать с ж-пой, а палец с пальцем. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	25.09.2018, 22:13
	renat_dmitriev, Вы когда за хлебом идёте всё время частный самолёт нанимаете? 0

@renat_dmitriev 392 / 294 / 121 Регистрация: 26.08.2016 Сообщений: 902
	25.09.2018, 22:53
	outoftime, Не по теме: Дайте пожалуйста ссылку на мой комментарий, где я просил вас читать мне лекции и нотации. Если такого комментария не существует, то давайте пожалуйста будет чуть более уважительны друг к другу и избавим форум от бессмысленного флуда. 0

Найти все пары натуральных дружественных чисел, меньших 50000.

Решение