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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.89
OverClocker
0 / 0 / 0
Регистрация: 16.03.2010
Сообщений: 17
20.04.2011, 10:14     Найти дружественные числа, принадлежащие отрезку [1; 10000] #1
Помогите, сегодня сдавать надо.

Дружественными числами являются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Например: 220 и 284 являются дружественными числами, поскольку сумма делителей числа 220 – это 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284, а сумма делителей числа 284 – это 1 + 2 + 4 + 71 + 142 = 220.
Найти дружественные числа, принадлежащие отрезку [1; 10000].

Заранее благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2011, 10:14     Найти дружественные числа, принадлежащие отрезку [1; 10000]
Посмотрите здесь:

C++ Дружественные числа
Используя датчик случайных чисел, получить координаты вершин треугольника x1, y1, x2, y2, x3, y3, принадлежащие отрезку [-5,5] C++
Даны действительные числа А,В,С . Найти те из них которые не принадлежат заданному отрезку [0; 2]. C++
Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [a,b]. C++
C++ простые числа от 1 до 10000
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
20.04.2011, 12:23     Найти дружественные числа, принадлежащие отрезку [1; 10000] #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;
}
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
20.04.2011, 15:02     Найти дружественные числа, принадлежащие отрезку [1; 10000] #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;
}
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
20.04.2011, 15:05     Найти дружественные числа, принадлежащие отрезку [1; 10000] #4
У меня время работы равно 0,515 секунды.
Вложения
Тип файла: rar screen.rar (10.8 Кб, 186 просмотров)
011
9 / 9 / 0
Регистрация: 28.11.2013
Сообщений: 146
16.03.2015, 20:30     Найти дружественные числа, принадлежащие отрезку [1; 10000] #5
outoftime, не могли бы вы (или кто-то другой) изложить алгоритм решения?

Добавлено через 8 часов 0 минут
Как найти все пары дружественных чисел на промежутке [1, ... , 100 000]?
Перебором -- слишком долго. Создать заранее массив дружественных чисел и потом брать из него -- не подходит.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
16.03.2015, 22:28     Найти дружественные числа, принадлежащие отрезку [1; 10000] #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
011
9 / 9 / 0
Регистрация: 28.11.2013
Сообщений: 146
17.03.2015, 19:56     Найти дружественные числа, принадлежащие отрезку [1; 10000] #7
ValeryS, подправил ваш код так, чтобы тестирующая система приняла (ваш код выводит одну и ту же пару по два раза, меняя порядок элементов).
Наихудшее время: 0,004 сек! Поясните, пожалуйста, идею)
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,042
17.03.2015, 20:20     Найти дружественные числа, принадлежащие отрезку [1; 10000] #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;
если число вывели как парное вычеркиваем из таблицы
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2016, 22:20     Найти дружественные числа, принадлежащие отрезку [1; 10000]
Еще ссылки по теме:

Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [a,b] C++
Организовать цикл do/while, который принимает целые числа с клавиатуры и вычитает их из 10000 C++
Дружественные перегрузки операторов и дружественные классы C++

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

Или воспользуйтесь поиском по форуму:
Vampir4i
0 / 0 / 0
Регистрация: 17.09.2015
Сообщений: 2
26.08.2016, 22:20     Найти дружественные числа, принадлежащие отрезку [1; 10000] #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;
    }
}
Понимаю что поздно выложил. Но вдруг кому-то пригодится. Написано все в одной функции по требованию одного человечка))
Yandex
Объявления
26.08.2016, 22:20     Найти дружественные числа, принадлежащие отрезку [1; 10000]
Ответ Создать тему
Опции темы

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