Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.61/88: Рейтинг темы: голосов - 88, средняя оценка - 4.61
0 / 0 / 1
Регистрация: 16.03.2010
Сообщений: 17
1

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

20.04.2011, 10:14. Показов 18349. Ответов 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

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

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.04.2011, 10:14
Ответы с готовыми решениями:

Положительные числа матрицы не принадлежащие заданному отрезку заменить на ноль
Данная целочисленная матрица А (5, 4). В матрице А все положительные числа, которые не принадлежат...

Найти числа, принадлежащие отрезку [a,b], количество делителей у которых является произведением двух простых чисел
Помогите пожалуйста написать коды для след. условий: 3.Найти натуральные числа, принадлежащие...

Дружественные числа до 10000
Здравствуйте. Помогите с задачкой: Найти все пары дружественных чисел до 10 000. Пара дружественных...

Выберите числа, принадлежащие заданному отрезку (блок схема)
Даны три числа. Выберите те из них, которые принадлежат заданному отрезку .

25
Эксперт С++
5044 / 3105 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
20.04.2011, 12:23 2
OverClocker, тупой перебор, но считает ооочень долго, первые две пары (а в промежутке [1; 10000] их всего пять) минуты за 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
#include <iostream>
 
typedef unsigned long long ull_t;
 
ull_t sum_of_divs(ull_t);
bool is_friendly(ull_t, ull_t);
 
int main()
{
    const ull_t left = 1;
    const ull_t right = 10000;
 
    for (ull_t num1 = left; num1 <= right; ++num1)
        for (ull_t num2 = num1 + 1; num2 <= right; ++num2)
            if (is_friendly(num1, num2))
                std::cout << num1 << "\t" << num2 << std::endl;
 
    return 0;
}
 
ull_t sum_of_divs(ull_t number)
{
    ull_t sum = 0;
 
    for (ull_t d = 1; d < number / 2 + 1; ++d)
        if (number % d == 0)
            sum += d;
 
    return sum;
}
 
bool is_friendly(ull_t number1, ull_t number2)
{
    return sum_of_divs(number1) == number2 && sum_of_divs(number2) == number1;
}
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
20.04.2011, 15:02 3
Интересная тема, пытаюсь оптимизировать:
[ссылка удалена]

Добавлено через 4 минуты
http://www.eunnet.net/books/numbers/text/14.html

 Комментарий модератора 
При всём уважении, правила всё-таки надо соблюдать.


Добавлено через 35 минут
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
/* 
 *  Author: Kovtun Ruslan
 *          TFTM 2011
 */
 
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <ctime>
#include <cmath>
 
using namespace std;
 
typedef __int64 LL;
typedef std::vector<int> VI;
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
VI prime;
 
void find_prime_to(const int &n){
    prime.resize(1, 2);
    for (int i = 3; i <= n; i += 2){
        int was = 0;
        FOR(j,0,prime.size()) 
            if (i % prime[j] == 0) was = 1;
            else if (was || prime[j] * prime[j] > i) break;
        if (!was) prime.push_back(i);
    }
}
 
LL BinPow(int a, int n){
    LL res = 1;
    while (n) n&1 ? (--n, res *= a) : (n >>= 1, a *= a);
    return res;
}
 
LL sum(const int &a){
    LL  res = 1, 
        i = 0, 
        d = a;
    map<int, int> m;
    while (d != 1){
        if (prime[i] * 1ll * prime[i] > a) 
            ++m[d], d = 1;
        else {
            while (d % prime[i] == 0)
                ++m[prime[i]], d /= prime[i];
        }
        ++i;
    }
    map<int, int>::iterator it;
    for (it = m.begin(); it != m.end(); ++it)
        res *= (BinPow(it->first, it->second + 1) - 1) / (it->first - 1);
    return res - a;
}
 
void solve(){
    int a, b;
    cin >> a >> b;
    find_prime_to(b);
    map<int, int> m, res;
    FOR(i,a,b+1) m[i] = sum(i);
    map<int, int>::iterator it, d;
    for (it = m.begin(); it != m.end(); ++it){
        if ((d = m.find(it->second)) != m.end() && it->first == d->second)
            res[min(it->first, it->second)] = max(it->first, it->second);
    }
    for (it = res.begin(); it != res.end(); ++it)
        cout << it->first << " and " << it->second << endl;
}
 
int main(){
    freopen("test.txt", "r", stdin);
 
    double start = clock() * 1.0 / CLOCKS_PER_SEC;
    solve();
    double end = clock() * 1.0 / CLOCKS_PER_SEC;
    cout << end - start << "sec" << endl;
}
1
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
20.04.2011, 15:05 4
У меня время работы равно 0,515 секунды.
0
Вложения
Тип файла: rar screen.rar (10.8 Кб, 234 просмотров)
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
16.03.2015, 20:30 5
outoftime, не могли бы вы (или кто-то другой) изложить алгоритм решения?

Добавлено через 8 часов 0 минут
Как найти все пары дружественных чисел на промежутке [1, ... , 100 000]?
Перебором -- слишком долго. Создать заранее массив дружественных чисел и потом брать из него -- не подходит.
0
Модератор
Эксперт по электронике
8471 / 6300 / 852
Регистрация: 14.02.2011
Сообщений: 21,847
16.03.2015, 22:28 6
вот не совсем перебор
создаю таблицу
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
#include <iostream>
#include <time.h>
int main()
{
const int N=100000;
int* arr=new int[N+1];
 
double start = clock() * 1.0 / CLOCKS_PER_SEC;
 
for(int i=0;i<=N;i++)
{
arr[i]=0;
}
 
 
for(int i=1;i<=N;i++)
{
 
for(int j=i+i;j<=N;j+=i)
    arr[j]+=i;
}
for(int i=1;i<=N;i++)
{
if(arr[i]<=N && arr[i]!=i && arr[arr[i]]==i)
  std::cout<< arr[i]<<"  "<<i<<std::endl;
 
}
 
 
delete []arr;
 
double end = clock() * 1.0 / CLOCKS_PER_SEC;
  std::cout << end - start << "sec" << std::endl;
 
return 0;
 
}
для 100000 0.03 сек
для 100000000 48 секунд
недостаток выводит парами
например
220 284
284 220
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
17.03.2015, 19:56 7
ValeryS, подправил ваш код так, чтобы тестирующая система приняла (ваш код выводит одну и ту же пару по два раза, меняя порядок элементов).
Наихудшее время: 0,004 сек! Поясните, пожалуйста, идею)
0
Модератор
Эксперт по электронике
8471 / 6300 / 852
Регистрация: 14.02.2011
Сообщений: 21,847
17.03.2015, 20:20 8
Цитата Сообщение от 011 Посмотреть сообщение
(ваш код выводит одну и ту же пару по два раза, меняя порядок элементов
легко меняется
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>
#include <time.h>
int main()
{
const int N=100000;
int* arr=new int[N+1];
 
double start = clock() * 1.0 / CLOCKS_PER_SEC;
 
for(int i=0;i<=N;i++)
{
arr[i]=0;
}
 
int m=N/2;
for(int i=1;i<=m;i++)
{
 
for(int j=i+i;j<=N;j+=i)
    arr[j]+=i;
}
for(int i=1;i<=N;i++)
{
if(arr[i]<=N && arr[i]!=i && arr[arr[i]]==i)
   {
  std::cout<< arr[i]<<"\t  "<<i<<std::endl;
   arr[i]=0;
  }
 
}
 
 
delete []arr;
 
double end = clock() * 1.0 / CLOCKS_PER_SEC;
  std::cout << end - start << "sec" << std::endl;
 
return 0;
 
}
вот подправленный код
Цитата Сообщение от 011 Посмотреть сообщение
Поясните, пожалуйста, идею
все дело в таблице которую я создаю
1 создаю таблицу размером в количество цифр+1 элемент(для нулевого значения)
2 обнуляю её
3 дальше заполняю суммами
Цитата Сообщение от ValeryS Посмотреть сообщение
C++
1
2
3
4
5
for(int i=1;i<=N;i++)
{
    for(int j=i+i;j<=N;j+=i)
        arr[j]+=i;
}
чтобы было понятно приведу пример на N=10
0 0 0 0 0 0 0 0 0 0 0
начиная с числа 1, внешний цикл это числа
внутренний цикл это смещение в таблице и шаг
поскольку делитель не равен числу то начинаем со следующего (j=i+i)
добавляю к элементу таблицы число
для 1 (начинаем со второго прибавляем 1)= 0 0 1 1 1 1 1 1 1 1 1
для 2 (начинаем с четвертого прибавляем 2)=0 0 1 1 3 1 3 1 3 1 3
для 3=(начинаем с шестого прибавляем 3)= 0 0 1 1 1 1 6 1 1 4 3
для 4 =(начинаем с восьмого прибавляем 4)= 0 0 1 1 3 1 6 1 7 4 3
для 4 =(начинаем с десятого прибавляем 5)= 0 0 1 1 3 1 6 1 7 4 8

таблица сумм готова
далее проверка
Цитата Сообщение от ValeryS Посмотреть сообщение
C++
1
if (arr[i]<=N && arr[i]!=i && arr[arr[i]]==i)
arr[i]<=N если сумма больше чем элементов массива делать нечего выходим
arr[i]!=i это выбрасывает числа сумма делителей которых равно самому числу например 6 1+2+3
arr[arr[i]]==i) а вот это проверка парности
смотрим например 220 и 284 arr[220]=284 arr[arr[220]]=arr[284]=220 равно i? да значит парное
в исправленном варианте я добавил arr[i]=0;
если число вывели как парное вычеркиваем из таблицы
4
0 / 0 / 0
Регистрация: 17.09.2015
Сообщений: 6
26.08.2016, 22:20 9
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
#include <iostream>
using namespace std;
 
void main()
{
    setlocale(LC_ALL, "Russian");
    int Sum;
    int tmpSum;
    int a, b, n;
    int i;
    cout << "Введите нижний предел: ";
    cin >> a;
    cout << "Введите верхний предел: ";
    cin >> b;
    for (n = a; n <= b; n++)
    {
        Sum = 0;
        tmpSum = 0;
        for (i = 1; i < n;i++)
        {
            if (n%i == 0)
            {
                Sum += i;
            }
        }
 
        for (i = 1; i < Sum; i++)
        {
            if (Sum%i == 0)
            {
                tmpSum += i;
            }
        }
        if (n == tmpSum)
            cout << n << '-' << Sum << endl;
    }
}
Понимаю что поздно выложил. Но вдруг кому-то пригодится. Написано все в одной функции по требованию одного человечка))
0
1 / 1 / 0
Регистрация: 20.02.2018
Сообщений: 2
20.02.2018, 19:05 10
#include <iostream>
using namespace std;
int main()
{
setlocale(0, "rus");
cout << "Программа находит и выводит на экран пары дружественных чисел(включая совершенные) из диапазона указанного пользователем." << endl << endl;
cout << "Enter the size: ";
int size;
cin >> size;
int resul = 0;
int res2 = 0;
for (int i = 1; i < size; i++)
{
resul = 0;
for(int j = 1;j < i; j++)
{
if(i % j == 0)
{
resul += j;
}
}
res2 = 0;
for(int l = 1;l < resul; l++)
{
if(resul % l == 0)
{
res2 += l;
}
}
if(i == res2)
cout << res2 << " - " << resul << endl;
}
cout << endl;
cout << endl;
return 0;
}
0
Модератор
Эксперт по электронике
8471 / 6300 / 852
Регистрация: 14.02.2011
Сообщений: 21,847
20.02.2018, 20:40 11
N13M12, так это же перебор
сколько времени занимает вывод до
Цитата Сообщение от OverClocker Посмотреть сообщение
[1; 10000].
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
20.02.2018, 20:48 12
Цитата Сообщение от outoftime Посмотреть сообщение
Интересная тема, пытаюсь оптимизировать:
А что там оптимизировать то.
Все простые числа меньшие 10000, являются дружественными.
Все простые числа умноженные на 2 и меньшие 10000 также являются дружественными.
И продолжайте эту тему до 10000.

Никакой оптимизации тут не надо.
0
Модератор
Эксперт по электронике
8471 / 6300 / 852
Регистрация: 14.02.2011
Сообщений: 21,847
20.02.2018, 20:54 13
Цитата Сообщение от Просто Саша Посмотреть сообщение
Все простые числа меньшие 10000, являются дружественными.
например 3 и 7
как известно у простых два делителя единица и само число
значит все простые дружественны 1,но 1 не дружествен никому поскольку
Цитата Сообщение от OverClocker Посмотреть сообщение
равно сумме всех натуральных делителей другого, исключая само это другое число.
у 1 сумма 0
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
20.02.2018, 21:05 14
ValeryS, Просто Саша, N13M12, сезон зомби тем открыли а мне не сказали?
0
ValeryS
20.02.2018, 21:08
  #15

Не по теме:

outoftime, так двойное зомби:) ты писал в 2011 я 2015 а сейчас 2018
цикличность однако:)

0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
20.02.2018, 21:20 16
Цитата Сообщение от Просто Саша Посмотреть сообщение
А что там оптимизировать то.
Всё верно, уже всё оптимизировано, время 0.5 это не долго

Добавлено через 53 секунды
Найти дружественные числа, принадлежащие отрезку [1; 10000] смотрим код, удивляемя какой он классный и закрываем вкладку
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
20.02.2018, 21:22 17
Цитата Сообщение от ValeryS Посмотреть сообщение
у 1 сумма 0
Ну это уже мелочи.
Тут важна идея.
0
Модератор
Эксперт по электронике
8471 / 6300 / 852
Регистрация: 14.02.2011
Сообщений: 21,847
20.02.2018, 21:23 18
Цитата Сообщение от Просто Саша Посмотреть сообщение
Тут важна идея.
так в чем идея то?
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
20.02.2018, 22:16 19
Цитата Сообщение от ValeryS Посмотреть сообщение
так в чем идея то?

Не по теме:

Да по большому то счету так себе идейка, ну уж какая задача, такая и идея.

0
19 / 18 / 2
Регистрация: 19.06.2019
Сообщений: 45
18.08.2019, 20:40 20
ValeryS, спасибо большое! Все кратко и понятно. А то я долго мучался и не мог понять как решать эту задачу.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.08.2019, 20:40

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

Вывести на экран все числа, принадлежащие отрезку [m, n] и кратные 7
Доброго времени суток. Возник вопрос с этой задачей. Нужно сделать в форме, однако можно написать...

Вывести на экран все простые числа , принадлежащие числовому отрезку от A до B
Вывести на экран все простые числа , принадлежащие числовому отрезку от A до B

Заменить на нули числа, принадлежащие заданному отрезку, и на единицы - остальные
Помогите, пожалуйста. Даны три действительных числа x, y, z и отрезок . Заменить на нули те из...

Напечатайте на экране монитора числа, принадлежащие отрезку [1; 99] и кратные числу 3
Напечатайте на экране монитора числа, принадлежащие отрезку и кратные числу 3.


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

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

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