Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
OverClocker
0 / 0 / 0
Регистрация: 16.03.2010
Сообщений: 17
#1

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

20.04.2011, 10:14. Просмотров 4873. Ответов 18
Метки нет (Все метки)

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

Дружественными числами являются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Например: 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2011, 10:14
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти дружественные числа, принадлежащие отрезку [1; 10000] (C++):

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

Используя датчик случайных чисел, получить координаты вершин треугольника x1, y1, x2, y2, x3, y3, принадлежащие отрезку [-5,5] - C++
Составьте программу для выполнения следующих заданий: 1. Ввести с клавиатуры длины отрезков a, b и c. 2. Проверить, могут ли быть...

Даны действительные числа А,В,С . Найти те из них которые не принадлежат заданному отрезку [0; 2]. - C++
Даны действительные числа А,В,С . Найти те из них которые не принадлежат заданному отрезку . кто напишет правильно программу тому...

Дружественные числа - C++
Мне нужно составить программу для нахождения дружечтвенных числ до заранее заданного числа n. Подскажите хоть как єто сделать, а то я даже...

Дружественные перегрузки операторов и дружественные классы - C++
#include <iostream> using namespace std; class person; class book { public: book(){}; int get_inf(person &a); void...

простые числа от 1 до 10000 - C++
Написать программу, которая выводит на экран все простые числа в диапазоне от 1 до 10000 и находит их количество.

18
silent_1991
Эксперт С++
5003 / 3061 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
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
outoftime
║XLR8║
753 / 653 / 88
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 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
outoftime
║XLR8║
753 / 653 / 88
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
20.04.2011, 15:05 #4
У меня время работы равно 0,515 секунды.
0
Вложения
Тип файла: rar screen.rar (10.8 Кб, 195 просмотров)
011
9 / 9 / 0
Регистрация: 28.11.2013
Сообщений: 152
16.03.2015, 20:30 #5
outoftime, не могли бы вы (или кто-то другой) изложить алгоритм решения?

Добавлено через 8 часов 0 минут
Как найти все пары дружественных чисел на промежутке [1, ... , 100 000]?
Перебором -- слишком долго. Создать заранее массив дружественных чисел и потом брать из него -- не подходит.
0
ValeryS
Модератор
6918 / 5261 / 512
Регистрация: 14.02.2011
Сообщений: 17,691
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
011
9 / 9 / 0
Регистрация: 28.11.2013
Сообщений: 152
17.03.2015, 19:56 #7
ValeryS, подправил ваш код так, чтобы тестирующая система приняла (ваш код выводит одну и ту же пару по два раза, меняя порядок элементов).
Наихудшее время: 0,004 сек! Поясните, пожалуйста, идею)
0
ValeryS
Модератор
6918 / 5261 / 512
Регистрация: 14.02.2011
Сообщений: 17,691
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;
если число вывели как парное вычеркиваем из таблицы
3
Vampir4i
0 / 0 / 0
Регистрация: 17.09.2015
Сообщений: 6
Завершенные тесты: 1
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
N13M12
0 / 0 / 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
ValeryS
Модератор
6918 / 5261 / 512
Регистрация: 14.02.2011
Сообщений: 17,691
20.02.2018, 20:40 #11
N13M12, так это же перебор
сколько времени занимает вывод до
Цитата Сообщение от OverClocker Посмотреть сообщение
[1; 10000].
0
Просто Саша
14 / 14 / 3
Регистрация: 27.11.2017
Сообщений: 221
Завершенные тесты: 2
20.02.2018, 20:48 #12
Цитата Сообщение от outoftime Посмотреть сообщение
Интересная тема, пытаюсь оптимизировать:
А что там оптимизировать то.
Все простые числа меньшие 10000, являются дружественными.
Все простые числа умноженные на 2 и меньшие 10000 также являются дружественными.
И продолжайте эту тему до 10000.

Никакой оптимизации тут не надо.
0
ValeryS
Модератор
6918 / 5261 / 512
Регистрация: 14.02.2011
Сообщений: 17,691
20.02.2018, 20:54 #13
Цитата Сообщение от Просто Саша Посмотреть сообщение
Все простые числа меньшие 10000, являются дружественными.
например 3 и 7
как известно у простых два делителя единица и само число
значит все простые дружественны 1,но 1 не дружествен никому поскольку
Цитата Сообщение от OverClocker Посмотреть сообщение
равно сумме всех натуральных делителей другого, исключая само это другое число.
у 1 сумма 0
0
outoftime
║XLR8║
753 / 653 / 88
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
20.02.2018, 21:05 #14
ValeryS, Просто Саша, N13M12, сезон зомби тем открыли а мне не сказали?
0
ValeryS
20.02.2018, 21:08     Найти дружественные числа, принадлежащие отрезку [1; 10000]
  #15

Не по теме:

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2018, 21:08
Привет! Вот еще темы с ответами:

Организовать цикл do/while, который принимает целые числа с клавиатуры и вычитает их из 10000 - C++
do - while Организовать цикл, который принимает целые числа с клавиатуры и вычитает их из 10000. Окончание цикла - получение...

Найти ошибку (класс дружественные классы) - C++
Пишет что то вроде неправильное обращение #include &lt;iostream&gt; #include &lt;cstring&gt; #include &lt;cstdlib&gt; using namespace std; ...

Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [a,b]. - C++
не знаю си++, но так вышло что надо для универа решить хотя бы две задачки, если кто поможет буду благодарен.Вот сами задачки. 1.Даны...

Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [a,b] - C++
Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку . помогите пожалуйста)))


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

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

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