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

Найти делители "длинного" числа - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
movielucky
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 6
15.07.2014, 11:03     Найти делители "длинного" числа #1
Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.07.2014, 11:03     Найти делители "длинного" числа
Посмотрите здесь:

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений C++
C++ 2 Программы. На "целые числа и системы счисления" и на "метод деления отрезка пополам"
C++ Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол"
C++ Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей";
C++ Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5547 / 2561 / 233
Регистрация: 01.11.2011
Сообщений: 6,330
Завершенные тесты: 1
15.07.2014, 11:38     Найти делители "длинного" числа #2
В столбик.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
15.07.2014, 11:40     Найти делители "длинного" числа #3
откуда возникла такая задача? как решать то я не знаю, но у числа длиной 12000 может быть дофига делителей!!!
если грубо оценить, то 2 * sqrt(n), но вообще слышал оценку что у числа n примерно n^(1 / 3) делителей, если не ошибаюсь. 10^4000 делителей? как их сохранить?
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5547 / 2561 / 233
Регистрация: 01.11.2011
Сообщений: 6,330
Завершенные тесты: 1
15.07.2014, 11:44     Найти делители "длинного" числа #4
Цитата Сообщение от SlavaSSU Посмотреть сообщение
как их сохранить?
Можно попробовать запомнить - ассоциативные методики запоминания позволяют запомнить очень дофига бессмысленных цифр подряд.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
15.07.2014, 12:21     Найти делители "длинного" числа #5
а нет, сейчас так проверил на нескольких числах. кубический корень - слишком много, там меньше получается.
т.е. в основном это сильно меньше чем куб корень, но все равно может быть дофига.
2 * 3 * 5 * ... * p[k];
вот так вот умножаешь последовательно простые, пока результат не станет больше исходного числа, пусть длина такого произведения равна k, тогда у числа есть примерно 2 ^ k делителей.
dogg12
 Аватар для dogg12
57 / 23 / 5
Регистрация: 21.02.2011
Сообщений: 503
15.07.2014, 16:53     Найти делители "длинного" числа #6
попробуйте применить алгоритм перебора делителей
avg93
61 / 61 / 10
Регистрация: 11.12.2009
Сообщений: 247
Завершенные тесты: 3
15.07.2014, 17:58     Найти делители "длинного" числа #7
Цитата Сообщение от movielucky Посмотреть сообщение
Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику?
А как без длинной арифметики тут? Нужны алгоритмы деления длинных чисел.
dogg12
 Аватар для dogg12
57 / 23 / 5
Регистрация: 21.02.2011
Сообщений: 503
15.07.2014, 18:01     Найти делители "длинного" числа #8
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//////////////////////////////////////////////////////////////////////////////////////
//Необходимо разделить большое чило на большое число.
//Эти числа хранятся в массиве (каждый элемент - одна цифра числа).
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_num_s;
//////////////////////////////////////////////////////////////////////////////////////
void  del_leading_zero(T_num_s&  a)
{
    while(a.size() > 1
          && a[0] == '0')
    {
        a.erase(0, 1);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
bool less_for_big_int(T_num_s  a, T_num_s  b)
{
    del_leading_zero(a);
    del_leading_zero(b);
 
    return  a.size() == b.size() ? a < b : a.size() < b.size();
}
//////////////////////////////////////////////////////////////////////////////////////
void  reduce_big_int(T_num_s&  minuend, const T_num_s&  subtrahend)
{    
    for(T_num_s::size_type  cur_pos = 0; cur_pos < subtrahend.size(); ++cur_pos)
    {
        T_num_s::size_type  minuend_cur_pos     = minuend.size()     - 1 - cur_pos;
        T_num_s::size_type  subtrahend_cur_pos  = subtrahend.size()  - 1 - cur_pos;
 
        char&        cur_minuend_dig_ref     = minuend     [minuend_cur_pos];
        const char&  cur_subtrahend_dig_ref  = subtrahend  [subtrahend_cur_pos];
 
        if(cur_minuend_dig_ref >= cur_subtrahend_dig_ref)
        {
            cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0';
        }
        else
        {
            (cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0') += 10;
            for(int i = 1; ; ++i)
            {
                if(minuend[minuend_cur_pos - i] == '0')
                {
                    minuend[minuend_cur_pos - i] = '9';
                }
                else
                {
                    --minuend[minuend_cur_pos - i];
                    break;
                }
            }
        }
        del_leading_zero(minuend);
    }
    del_leading_zero(minuend);
}
//////////////////////////////////////////////////////////////////////////////////////
void  inc_big_int(T_num_s&  a)
{    
    for(T_num_s::size_type  cur_pos = a.size() - 1;; --cur_pos)
    {
        if(a[cur_pos] < '9')
        {
            ++a[cur_pos];
            return;
        }
        else
        {
            a[cur_pos] = '0';
            if(cur_pos == 0)
            {              
                a.insert(0, "1");
                return;
            }
        }    
    }
}
//////////////////////////////////////////////////////////////////////////////////////
T_num_s  div_big_int(const T_num_s&  a, const T_num_s&  b)
{
    if(b == "0")
    {
        return  "division into zero";
    }    
 
    T_num_s  res = "0";
    T_num_s  minuend     = a;
    T_num_s  subtrahend  = b;
    
    while(subtrahend.size() < minuend.size())
    {
        subtrahend += '0';    
    }
 
    for(;;)
    {
        while(!less_for_big_int(minuend, subtrahend))
        {
            reduce_big_int(minuend, subtrahend);
            inc_big_int(res);
        }
        if(subtrahend.size() <= b.size())
        {
            break;
        }
        
        subtrahend.erase(subtrahend.size() - 1);   
        res += '0';              
        del_leading_zero(res);
    }          
    
    return  res;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    for(;;)
    {
        std::cout << "a = ";
        T_num_s  a;
        std::cin >> a;
        del_leading_zero(a);
 
        std::cout << "b = ";
        T_num_s  b;
        std::cin >> b;
        del_leading_zero(b);
 
        std::cout << "a / b = "
                  << div_big_int(a, b)
                  << std::endl
                  << std::endl
                  << std::endl;    
    }
}
NEbO
15.07.2014, 18:31
  #9

Не по теме:

40к бит? ха. а может уж сразу ключик выпишите, а мы тут все вместе вам его факторизуем?

Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,655
15.07.2014, 19:35     Найти делители "длинного" числа #10
dogg12, я вам признателен, что вы процитировали мою программу, но это решение задачи разделить одно длинное число на другое. В данной задаче делений гораздо больше, поэтому она по скорости не подойдет.
dogg12
 Аватар для dogg12
57 / 23 / 5
Регистрация: 21.02.2011
Сообщений: 503
15.07.2014, 19:50     Найти делители "длинного" числа #11
Можно попробовать перейти к двоичной арифметике, как писали выше для деления "в столбик", т.к. алгоритм при таком подходе упрощается.
Sergio Leone
2446 / 1091 / 398
Регистрация: 07.06.2014
Сообщений: 3,240
15.07.2014, 22:54     Найти делители "длинного" числа #12
dogg12, Вы ещё не поняли, в чём затык?
Делители нужно искать в цикле, да?
Попробуйте, для начала,организовать цикл, ну, скажем, до сектилиона.
Напоминаю, что секстиллион это http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{21} (см.вики)
т.е. это число 1000000000000000000000

а теперь допишите ноликов ещё примерно 5 тысяч штук. И подумайте, сколько будем выполняться такой цикл.
dogg12
 Аватар для dogg12
57 / 23 / 5
Регистрация: 21.02.2011
Сообщений: 503
15.07.2014, 23:15     Найти делители "длинного" числа #13
Я понял, но смотрите, у меня такая мысль: будем выполнять деление в столбик.
Переведем числа в двоичную систему.
Сдвигаем делитель влево до тех пор, пока старший бит не станет 1, запоминаем количество сдвигов.
Повторяем столько раз, сколько было сдвигов.
Если делитель (модифицированный) меньше делимого, то вычитаем его из делимого, очередной бит ответа — 1
иначе очередной бит ответа — 0.
Сдвигаем делитель вправо.
Если нет возможности перейти к двоичной арифметике, алгоритм усложнится, потому что на каждом шаге основного цикла надо будет не просто сравнивать делимое с делителем, а вычислять очередную цифру ответа. Для десятичных чисел сдвиг влево — это дополнение делителя справа нулем.
Я не спорю, есть и более скоростные алгоритмы, которые основаны на обработке не одного бита за раз, а сразу группы бит (2, 4, 8), но они сложнее.
Sergio Leone
2446 / 1091 / 398
Регистрация: 07.06.2014
Сообщений: 3,240
15.07.2014, 23:24     Найти делители "длинного" числа #14
Цитата Сообщение от dogg12 Посмотреть сообщение
Я не спорю, есть и более скоростные алгоритмы, которые основаны на обработке не одного бита за раз, а сразу группы бит (2, 4, 8), но они сложнее.
так. ещё раз.
Допустим, ваш компьютер за один такт процессора проверяет делится ли одно длинное число на другое.
Тогда Вы за одну секунду можете проверить 4 миллиарда длинных чисел (4 ГГц). Это http://www.cyberforum.ru/cgi-bin/latex.cgi?4 * {10}^{9}
Подсчитайте, пожалуйста, сколько потребуется секунд, чтобы проверить на делимость http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6000} чисел.
Полученное число секунд переведите в число лет.
И поймёте, о чём здесь говорят, когда утверждают, что не хватит времени на выполнение цикла.
dogg12
 Аватар для dogg12
57 / 23 / 5
Регистрация: 21.02.2011
Сообщений: 503
15.07.2014, 23:26     Найти делители "длинного" числа #15
Тогда подобный вопрос должен стоять явно не в разделе для начинающих)
Sergio Leone
2446 / 1091 / 398
Регистрация: 07.06.2014
Сообщений: 3,240
15.07.2014, 23:30     Найти делители "длинного" числа #16
Цитата Сообщение от dogg12 Посмотреть сообщение
Тогда подобный вопрос должен стоять явно не в разделе для начинающих)
Так автор этого вопроса явно не видит в нём никаких проблем


кстати, он создал дублирующую тему в разделе Java. Ему неважно, на C++ ему напишут программу или на Java. Главное, чтобы она нашла все делители его числа. Он и не подозревает, что скорее наше солнце погаснет, чем программа досчитает до конца.
dogg12
 Аватар для dogg12
57 / 23 / 5
Регистрация: 21.02.2011
Сообщений: 503
15.07.2014, 23:37     Найти делители "длинного" числа #17
Это у нас с вами "простые компьютеры", может человек работает в каком-нибудь супер-пупер мощном вычислительным центре, где большое количество навороченных ЭВМ справятся с такой задачей. Обычно подобные вопросы в таких местах и решают. Люди в НИИ работают над этим годами, а тут на форуме спрашивают... Человечество прогрессирует так сказать)
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
15.07.2014, 23:44     Найти делители "длинного" числа #18
Sergio Leone, Да ладно, кто-то же должен изобретать bogo sort и подобные алгоритмы

movielucky, предлагаю находить хэш от строки из 12 тыс символов, после этого обработать его как-нибудь (умножить/разделить и т.п.) и распечатать как вывод. Если преподаватель засомневается, попросите его перепроверить результат. Пятерка вам гарантированна!

Добавлено через 4 минуты
dogg12, самый мощный компьютер в мире имеет производительность около 20 петафлопс. Принимая допущения выше, 106000/1020... На самом деле, тут не особо важна мощностью компьютера. Компьютер с мощностью 1 флопс проверит за 106000 секунд, а супер-компьютер, который имеет триллион квадралионов флопсов (1012 *1015) проверит число за 105973 секунд (при этом такая производительность сегодня даже в самых смелых мечтах не видится, это в миллион раз мощнее самого мощного суперкомпьютера современности). Так что не принципиально, на кор ай семь или зеоне считается, или на интел 8087, тепловая смерть вселенной наступит намного раньше
zer0mail
2182 / 1865 / 187
Регистрация: 03.07.2012
Сообщений: 6,630
Записей в блоге: 1
16.07.2014, 18:10     Найти делители "длинного" числа #19
Ищи простые делители с кратностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 18:19     Найти делители "длинного" числа
Еще ссылки по теме:

C++ Многократное "длинное" деление (длинного на короткое)
Нужно сделать так, чтобы при вводе числа, выводило "рублей" или "рубль" C++
C++ Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку

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

Или воспользуйтесь поиском по форуму:
volvo
Супер-модератор
 Аватар для volvo
21685 / 14158 / 3939
Регистрация: 22.10.2011
Сообщений: 25,019
Записей в блоге: 2
16.07.2014, 18:19     Найти делители "длинного" числа #20
zer0mail, сколько времени твоей программе понадобится, чтобы найти делители числа:
Код
146783911423364576743092536350764769178885886396876485026777655885608637226256065354828356063571819406295041
?
Yandex
Объявления
16.07.2014, 18:19     Найти делители "длинного" числа
Ответ Создать тему
Опции темы

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