Форум программистов, компьютерный форум CyberForum.ru

Напечатать все пары дружественных чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
user_p01
19 / 19 / 2
Регистрация: 03.11.2011
Сообщений: 80
03.09.2012, 15:40     Напечатать все пары дружественных чисел #1
Помогите пожалуйста решить рационально задачу:

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

Мой вариант работает правильно, но очень медленно, т. к. слишком много итераций. Подскажите как решить эту задачу, чтобы программа работала быстрее.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int sum_del(int n)
{
 int sum=0;
 for (int i=1; i<=n/2; i++)
 if (n%i==0)
    sum+=i;
 return sum;
}
int main()
{
    setlocale(LC_ALL, "rus");
    int n, i, j;
    cout << "Введите число: ";
    cin >> n;
    for (i=1; i<n-1; i++)
        for (j=i+1; j<n; j++)
        if (i==sum_del(j) && j==sum_del(i))
            cout << i << "\t" << j << endl; 
 system("pause");
 return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.09.2012, 15:40     Напечатать все пары дружественных чисел
Посмотрите здесь:

C++ Найти все пары «дружественных чисел», которые не больше данного числа
Найти все пары дружественных чисел в диапазоне от 200 до 300 C++
Найти все пары «дружественных чисел», которые не больше данного числа/ на C++ C++
Напечатать все пары чисел-близнецов, не превышающих число 200 C++
C++ Найти все пары дружественных чисел, не превосходящих заданного натурального числа N
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2012, 15:44     Напечатать все пары дружественных чисел #2
Вы O(n^2) раз ищите делители. Это очень много. Можно по-другому. В массив A размера N сначала записываете сумму делителей, то есть A[i] = сумма делителей числа i. А потом работаете уже с этим массивом. Много быстрее будет. Немного переделал вашу программу:

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>
using namespace std;
int sum_del(int n)
{
 int sum=0;
 for (int i=1; i<=n/2; i++)
 if (n%i==0)
    sum+=i;
 return sum;
}
int main()
{
    setlocale(LC_ALL, "rus");
    int n, i, j, *a;
    cout << "Ââåäèòå ÷èñëî: ";
    cin >> n;
    a = new int[n];
    for (i=1; i<n; i++)
       a[i] = sum_del(i);
    for (i=1; i<n-1; i++)
        for (j=i+1; j<n; j++)
        if (i==a[j] && j==a[i])
            cout << i << "\t" << j << endl;
 system("pause");
 return 0;
}
user_p01
19 / 19 / 2
Регистрация: 03.11.2011
Сообщений: 80
03.09.2012, 15:49  [ТС]     Напечатать все пары дружественных чисел #3
Спасибо большое за помощь!
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2012, 15:49     Напечатать все пары дружественных чисел #4
Цитата Сообщение от user_p01 Посмотреть сообщение
Спасибо. Можно фрагмент кода?
да, сверху он.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
03.09.2012, 20:28     Напечатать все пары дружественных чисел #5
да и делители можно быстрее искать
C++
1
2
3
4
5
6
7
8
9
10
11
int getSum(int n) {
    int sum = 0;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            sum += i;
            if (i * i != n)
                sum += n / i;
        }
    }
    return sum;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2012, 20:44     Напечатать все пары дружественных чисел #6
neske, Вы правы. Но так как ищутся делители у всех чисел от 1 до n, то можно, учитывая однозначность канонического разложения, использовать решето Эратосфена, тогда вообще без делений будет. Первичная цель была убрать повторные вычисления сумм. Если бы ТС было это недостаточно, можно было идти дальше. Но все равно, спасибо за ценное замечание.

Добавлено через 10 минут
neske, алгоритм неверно считает, например для 9 выдает 13. Думаю, что лучше так

C++
1
2
3
4
5
6
7
8
9
10
11
12
int getSum(int n) {
    int i, sum = 1;
    for (i = 2; i * i < n; ++i) {
        if (n % i == 0) {
            sum += i;
            sum += n / i;
        }
    }
    if (i * i == n)
       sum += i;
    return sum;
}
да еще и проверок в нем меньше. В алгоритме не должно само число n учитываться. А если все делители, то можно так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int getSum(int n) {
    int i, sum = 1;
    for (i = 2; i * i < n; ++i) {
        if (n % i == 0) {
            sum += i;
            sum += n / i;
        }
    }
    if (i * i == n)
       sum += i;
    if (n != 1)
       sum += n;
    return sum;
}
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
03.09.2012, 20:59     Напечатать все пары дружественных чисел #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
а, ну да, само число не учитывать, тогда так можно -
C++
1
2
3
4
5
6
7
8
9
10
11
int getSum(int n) {
    int sum = 1;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            sum += i;
            if (i * i != n)
                sum += n / i;
        }
    }
    return sum;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2012, 13:35     Напечатать все пары дружественных чисел
Еще ссылки по теме:

Найти все пары дружественных натуральных чисел из интервала от N 1 до N 2. C++
C++ Найти все пары дружественных чисел, лежащих в диапазоне от 200 до 300
Из заданного интервала натуральных чисел выбрать и напечатать все пары дружественных чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.09.2012, 13:35     Напечатать все пары дружественных чисел #8
вообще, конечно алгоритм можно оптимизировать, исходя из первых простых чисел 2, 3, 5,..., p, только код объемнее будет, но быстрее.

Добавлено через 17 часов 39 минут
Немного подумал на досуге. Алгоритм можно линейным сделать. Вводите m и n и на отрезке от m до n найдутся все пары дружественных чисел. Например, для m=1, n=100000 алгоритм работает моментально.
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
#include <iostream>
 
long Sum(long n)
{
    long sum = 1, i, beg = 2, d = 1;
    if (n & 1)
    {
        d = 2;
        beg = 3;
    }
    for(i = beg; i*i < n; i += d)
        if (n % i == 0)
            sum += (i + n/i);
    if (i*i == n)
       sum += i;
    return sum;
}
 
int main()
{
    long m, n, i, *a;
    std::cin >> m >> n;
    a = new long[n - m + 1];
    for(i = 0; i <= n - m ; i++)
       a[i] = Sum(i + m);
 
    for(i = 0; i <= n - m ; i++)
       if(a[i] >= m && a[i] <= n &&  a[a[i] - m] == i + m && i + m < a[i])
          std::cout << i + m << " " << a[i] << std::endl;
    delete[] a;
    return 0;
}
Вся сложность пока в нахождении суммы делителей. Это не оптимальный вариант, но уже более-менее быстрый. И по массиву a достаточно 1 раз пройти.

Добавлено через 3 часа 7 минут
Алгоритм существует быстрого нахождения сумм делителей (ура, придумал!!!) на отрезке. Для любителей прекальков выкладываю
все дружественные числа на отрезке [1, 100000000]

220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416
63020 76084
66928 66992
67095 71145
69615 87633
79750 88730
100485 124155
122265 139815
122368 123152
141664 153176
142310 168730
171856 176336
176272 180848
185368 203432
196724 202444
280540 365084
308620 389924
319550 430402
356408 399592
437456 455344
469028 486178
503056 514736
522405 525915
600392 669688
609928 686072
624184 691256
635624 712216
643336 652664
667964 783556
726104 796696
802725 863835
879712 901424
898216 980984
947835 1125765
998104 1043096
1077890 1099390
1154450 1189150
1156870 1292570
1175265 1438983
1185376 1286744
1280565 1340235
1328470 1483850
1358595 1486845
1392368 1464592
1466150 1747930
1468324 1749212
1511930 1598470
1669910 2062570
1798875 1870245
2082464 2090656
2236570 2429030
2652728 2941672
2723792 2874064
2728726 3077354
2739704 2928136
2802416 2947216
2803580 3716164
3276856 3721544
3606850 3892670
3786904 4300136
3805264 4006736
4238984 4314616
4246130 4488910
4259750 4445050
4482765 5120595
4532710 6135962
4604776 5162744
5123090 5504110
5147032 5843048
5232010 5799542
5357625 5684679
5385310 5812130
5459176 5495264
5726072 6369928
5730615 6088905
5864660 7489324
6329416 6371384
6377175 6680025
6955216 7418864
6993610 7158710
7275532 7471508
7288930 8221598
7489112 7674088
7577350 8493050
7677248 7684672
7800544 7916696
7850512 8052488
8262136 8369864
8619765 9627915
8666860 10638356
8754130 10893230
8826070 10043690
9071685 9498555
9199496 9592504
9206925 10791795
9339704 9892936
9363584 9437056
9478910 11049730
9491625 10950615
9660950 10025290
9773505 11791935
10254970 10273670
10533296 10949704
10572550 10854650
10596368 11199112
10634085 14084763
10992735 12070305
11173460 13212076
11252648 12101272
11498355 12024045
11545616 12247504
11693290 12361622
11905504 13337336
12397552 13136528
12707704 14236136
13671735 15877065
13813150 14310050
13921528 13985672
14311688 14718712
14426230 18087818
14443730 15882670
14654150 16817050
15002464 15334304
15363832 16517768
15938055 17308665
16137628 16150628
16871582 19325698
17041010 19150222
17257695 17578785
17754165 19985355
17844255 19895265
17908064 18017056
18056312 18166888
18194715 22240485
18655744 19154336
20014808 21457192
20022328 22823432
20308995 20955645
21448630 23030090
22227075 24644925
22249552 25325528
22508145 23111055
22608632 25775368
23358248 25233112
23389695 25132545
23628940 27428276
24472180 30395276
25596544 25640096
25966832 26529808
26090325 26138475
28118032 28128368
28608424 29603576
30724694 32174506
30830696 31652704
31536855 32148585
31818952 34860248
32205616 34352624
32642324 35095276
32685250 34538270
33501825 36136575
34256222 35997346
34364912 34380688
34765731 36939357
35115795 43266285
35361326 40117714
35373195 40105845
35390008 39259592
35472592 36415664
37363095 45663849
37784810 39944086
37848915 39202605
38400512 38938288
38637016 40678184
38663950 43362050
38783992 41654408
38807968 40912232
43096904 46715896
44139856 44916944
45263384 46137016
46237730 61319902
46271745 49125375
46521405 53011395
46555250 55880590
46991890 48471470
48639032 52967368
48641584 48852176
49215166 55349570
50997596 51737764
52695376 56208368
56055872 56598208
56512610 75866014
56924192 64562488
58580540 70507972
59497888 61953512
63560025 65003175
63717615 66011985
66595130 74824390
66854710 71946890
67729064 69439576
67738268 79732132
68891992 78437288
71015260 85458596
71241830 78057370
72958556 74733604
73032872 78469528
74055952 78166448
74386305 87354495
74769345 82824255
75171808 77237792
75226888 81265112
78088504 88110536
78447010 80960990
79324875 87133365
80422335 82977345
83135650 85603550
84591405 89590995
86158220 99188788
89477984 92143456
90437150 94372450
91996816 93259184
93837808 99899792
95629904 97580944
96304845 96747315
97041735 97945785

программа работала пару секунд.

Добавлено через 19 часов 39 минут
У кого еще какие предложения по поводу того, что возможно ли быстрее чем за 2-3 секунды обработать http://www.cyberforum.ru/cgi-bin/latex.cgi?10^8 натуральных чисел в этой задаче. Задача очень интересная в том смысле, что многие участники олимпиад не придумали лучше чем сделать прекальк. А алгоритм то существует!!!
Yandex
Объявления
05.09.2012, 13:35     Напечатать все пары дружественных чисел
Ответ Создать тему
Опции темы

Текущее время: 08:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru