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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.89
OverClocker
0 / 0 / 0
Регистрация: 16.03.2010
Сообщений: 17
#1

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

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

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

Дружественными числами являются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Например: 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++
C++ Дружественные числа
Дружественные перегрузки операторов и дружественные классы C++
C++ простые числа от 1 до 10000
C++ Найти ошибку (класс дружественные классы)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
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║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
20.04.2011, 15:05     Найти дружественные числа, принадлежащие отрезку [1; 10000] #4
У меня время работы равно 0,515 секунды.
Вложения
Тип файла: rar screen.rar (10.8 Кб, 189 просмотров)
011
9 / 9 / 0
Регистрация: 28.11.2013
Сообщений: 152
16.03.2015, 20:30     Найти дружественные числа, принадлежащие отрезку [1; 10000] #5
outoftime, не могли бы вы (или кто-то другой) изложить алгоритм решения?

Добавлено через 8 часов 0 минут
Как найти все пары дружественных чисел на промежутке [1, ... , 100 000]?
Перебором -- слишком долго. Создать заранее массив дружественных чисел и потом брать из него -- не подходит.
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
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
Сообщений: 152
17.03.2015, 19:56     Найти дружественные числа, принадлежащие отрезку [1; 10000] #7
ValeryS, подправил ваш код так, чтобы тестирующая система приняла (ваш код выводит одну и ту же пару по два раза, меняя порядок элементов).
Наихудшее время: 0,004 сек! Поясните, пожалуйста, идею)
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
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]
Еще ссылки по теме:
Организовать цикл do/while, который принимает целые числа с клавиатуры и вычитает их из 10000 C++
Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [a,b] C++
Даны три числа. Выбрать те из них, которые принадлежат заданному отрезку [a,b]. C++
В порядке возрастания напечатать те целые числа из диапазона 1..10000, которые можно представить в указанном виде C++
Найти натуральное число от 1 до 10000 с максимальной суммой делителей. C++

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

Или воспользуйтесь поиском по форуму:
Vampir4i
0 / 0 / 0
Регистрация: 17.09.2015
Сообщений: 5
Завершенные тесты: 1
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]
Ответ Создать тему
Опции темы

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