Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/34: Рейтинг темы: голосов - 34, средняя оценка - 4.71
4 / 4 / 3
Регистрация: 14.01.2017
Сообщений: 284
1

В заданном диапазоне найти все пары натуральных дружественных чисел, удовлетворяющих условию

26.01.2017, 20:13. Показов 6305. Ответов 9
Метки нет (Все метки)

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

Вводится одно целое число N (1≤N≤10000).
Формат выходных данных

Требуется вывести все пары дружественных чисел, удовлетворяющие условию задачи. Пары можно выводить в любом порядке.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.01.2017, 20:13
Ответы с готовыми решениями:

В заданном массиве целых чисел найти все пары чисел, удовлетворяющих условию
Дан массив целых чисел а0, ..., аn-1. Найти все пары (аi, аi+1), такие, что аi = 0 и аi+1 кратно 2.

Найти все пары дружественных чисел в диапазоне [n1, n2]
Два натуральных числа называются дружественными, если каждое из них равно сумме простых делителей...

Найти все пары дружественных натуральных чисел из интервала от N 1 до N 2.
Очень нужна помощь!) Помогите пожалуйста) в С++, visual studio учусь на первом курсе мех-мата: ...

Найти все пары дружественных чисел в диапазоне от 200 до 300
Помогите пожалуйста с решением задачи в С++. Вот условие: используя оператор цикла for, решить...

9
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
26.01.2017, 22:43 2
ARTER616, здравствуйте! Я решил данную задачу, но программа очень медленно считает...Вот код:

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
#include <iostream>
 
using namespace std;
 
int SumD(int N)
{
    int sum = 0;
    for (int i = 1; i < N; i++)
    {
        if (!(N % i))
            sum += i;
    }
    return sum;
}
 
bool IfFriendly(int A, int B)
{
    if (A == SumD(B) && B == SumD(A))
        return true;
    return false;
}
 
int main()
{
    int N, k;
    cout << "Введите N: ";
    cin >> N;
    k = 0;
    cout << "Результат работы программы:" << endl;
    for (int i = 1; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            if (IfFriendly(i, j))
            {
                cout << i << " " << j << endl;
                k++;
            }
        }
    }
    if (!(k))
        cout << "Дружественных пар нет!" << endl;
    system("pause");
    return 0;
}
0
33 / 32 / 9
Регистрация: 16.04.2015
Сообщений: 275
27.01.2017, 02:40 3
Fixer_84, медленно оно считает, потому, что Вы перебираете все числа без каких-либо ограничений.
А ограничений много. Например, если одно оба числа простые, то они явно не пара.
(и делители искать незачем). ...а может достаточно и одному числу быть простым.
0
4 / 4 / 3
Регистрация: 14.01.2017
Сообщений: 284
27.01.2017, 16:11  [ТС] 4
А можете указать в какие конкретно строки нужно исправить?
0
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
27.01.2017, 19:45 5
SerVal, спасибо за вашу подсказку! ARTER616, вот нашел более оптимальное решение. Но при сдаче один тест по времени все равно завален
Напечатать все пары дружественных чисел

Добавлено через 3 минуты
ARTER616, P.S. Считает очень быстро

Добавлено через 24 минуты
ARTER616, http://math4school.ru/ohota_na... hisla.html
0
4 / 4 / 3
Регистрация: 14.01.2017
Сообщений: 284
27.01.2017, 20:05  [ТС] 6
А какой ответ там правильный? У меня почему-то ошибку выдает
0
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
27.01.2017, 20:25 7
ARTER616, там просто задается интервал от M до N. Замените M на 1 и вводите только N, Вот код:

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
#include <iostream>
 
using namespace std;
 
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, k;
    cin >> M >> N;
    long* A = new long[N - M + 1];
    for (int i = 0; i <= N - M; i++)
        A[i] = Sum(i + M);
    k = 0;
    for (int i = 0; i <= N - M; i++)
        if (A[i] >= M && A[i] <= N && A[A[i] - M] == i + M && i + M < A[i])
        {
            cout << i + M << " " << A[i] << endl;
            k++;
        }
    if (!(k))
        cout << "Absent" << endl;
    delete[] A;
    system("pause");
    return 0;
}
Добавлено через 4 минуты
ARTER616, вообщем, будет так:

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
#include <iostream>
 
using namespace std;
 
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, k;
    cin >> N;
    long* A = new long[N];
    for (int i = 0; i < N; i++)
        A[i] = Sum(i + 1);
    k = 0;
    for (int i = 0; i < N; i++)
        if (A[i] >= 1 && A[i] <= N && A[A[i] - 1] == i + 1 && i + 1 < A[i])
        {
            cout << i + 1 << " " << A[i] << endl;
            k++;
        }
    if (!(k))
        cout << "Дружественных чисел нет!" << endl;
    delete[] A;
    system("pause");
    return 0;
}
Добавлено через 2 минуты
ARTER616, Даже для N = 1000000 быстро находит.
2
4 / 4 / 3
Регистрация: 14.01.2017
Сообщений: 284
27.01.2017, 20:35  [ТС] 8
Спасибо!!!

Добавлено через 8 минут
А можно сделать еще чтобы выводило ответ и этот же ответ в обратном порядке? Например(220 284; 284 220)
-------------------
И еще при вводе 284 выдает неправильный ответ(такой же как при вводе 300, а должно вывести "Нет дружественных чисел")
0
1480 / 944 / 811
Регистрация: 30.04.2016
Сообщений: 3,298
27.01.2017, 20:59 9
Лучший ответ Сообщение было отмечено ARTER616 как решение

Решение

ARTER616, при вводе 284 я исправил (в 30 строчке поменял A[i] <= N на A[i] < N). Но при вводе 300 должно выдавать 220 284, так как оба числа < 300 (так сказано в условии задачи). Вот исправленный код:

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
#include <iostream>
 
using namespace std;
 
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, k;
    cout << "Введите N: ";
    cin >> N;
    long* A = new long[N];
    for (int i = 0; i < N; i++)
        A[i] = Sum(i + 1);
    k = 0;
    for (int i = 0; i < N; i++)
        if (A[i] >= 1 && A[i] < N && A[A[i] - 1] == i + 1 && i + 1 < A[i])
        {
            cout << i + 1 << " " << A[i] << "; " << A[i] << " " << i + 1 << endl;
 
            k++;
        }
    if (!(k))
        cout << "Дружественных чисел нет!" << endl;
    delete[] A;
    system("pause");
    return 0;
}
1
33 / 32 / 9
Регистрация: 16.04.2015
Сообщений: 275
28.01.2017, 13:42 10
Цитата Сообщение от ARTER616 Посмотреть сообщение
А можно сделать еще чтобы выводило ответ и этот же ответ в обратном порядке? Например(220 284; 284 220)
Тогда надо не сразу выводить на экран, а запихивать найденные пары в вектор.
Ну, а уж потом выводить как душа пожелает. Хоть с начала до конца, хоть наоборот.
*****

Проверил программку от ARTER616. Вроде бы всё верно находит:
Кликните здесь для просмотра всего текста

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
Amicable search: 10000000 .. 20000000
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
18655744 19154336
Found   : 33
Exec time   :   185.3 seconds.

На старом Intel Quad Q9650 3.0 GHz

Добавлено через 14 минут
Эх, Fixer_84, из хорошей программы сделали какой-то огрызок, который может считать только "от печки" - только от нуля.
*как сейчас в Инете - полно программ поиска простых чисел, которые могут считать их полько от 0 до N.
Такое надо? Интересно ж что-то "в диапазоне от и до".

Добавлено через 15 часов 6 минут
Народ, у кого какие результаты? Выкладывайте посмотрим.
Вот у меня на Intel Quad Q9650 3 Гигагерца
C++
1
2
3
4
5
6
7
8
9
10
D:\AmiSearch.exe
 
Amicable pair : 10000000 .. 11000000
 
10254970 10273670
10533296 10949704
10572550 10854650
 
Found    : 3
Exec time: 1.006 seconds.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.01.2017, 13:42

Найти все пары дружественных чисел в заданном диапазоне
1.Дружественные числа -– это два натуральных числа, таких, что сумма всех делителей одного числа...

Найти все пары дружественных чисел, лежащих в заданном диапазоне
Помогите, пожалуйста. Даны натуральные числа n и t. Найти все пары дружественных чисел, лежащих в...

Найти все пары дружественных чисел, лежащих в заданном диапазоне
18. Даны натуральные числа n и m. Найти все пары дружественных чисел, лежащих в диапазоне от n до...

Найти все пары натуральных дружественных чисел
Числовая дружба Составьте программу для решения задачи. Два натуральных числа называются...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.