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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
movielucky
0 / 0 / 0
Регистрация: 14.12.2013
Сообщений: 8
#1

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

15.07.2014, 11:03. Просмотров 1605. Ответов 24
Метки нет (Все метки)

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

Печатает очень большие числа в колонке "Y"" C++
C++ Найти все делители числа P
Найти все делители натурального числа n C++
Найти все делители натурального числа N C++
Найти все делители числа 1234 C++
C++ Необходимо найти и записать в стек числа, в состав которых входит 1 символ "*"
Найти в строке слово, начинающееся буквой "а" и оканчивающееся буквой "я" C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2583 / 235
Регистрация: 01.11.2011
Сообщений: 6,382
Завершенные тесты: 1
15.07.2014, 11:38     Найти делители "длинного" числа #2
В столбик.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
15.07.2014, 11:40     Найти делители "длинного" числа #3
откуда возникла такая задача? как решать то я не знаю, но у числа длиной 12000 может быть дофига делителей!!!
если грубо оценить, то 2 * sqrt(n), но вообще слышал оценку что у числа n примерно n^(1 / 3) делителей, если не ошибаюсь. 10^4000 делителей? как их сохранить?
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2583 / 235
Регистрация: 01.11.2011
Сообщений: 6,382
Завершенные тесты: 1
15.07.2014, 11:44     Найти делители "длинного" числа #4
Цитата Сообщение от SlavaSSU Посмотреть сообщение
как их сохранить?
Можно попробовать запомнить - ассоциативные методики запоминания позволяют запомнить очень дофига бессмысленных цифр подряд.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
15.07.2014, 12:21     Найти делители "длинного" числа #5
а нет, сейчас так проверил на нескольких числах. кубический корень - слишком много, там меньше получается.
т.е. в основном это сильно меньше чем куб корень, но все равно может быть дофига.
2 * 3 * 5 * ... * p[k];
вот так вот умножаешь последовательно простые, пока результат не станет больше исходного числа, пусть длина такого произведения равна k, тогда у числа есть примерно 2 ^ k делителей.
dogg12
 Аватар для dogg12
59 / 25 / 6
Регистрация: 21.02.2011
Сообщений: 571
15.07.2014, 16:53     Найти делители "длинного" числа #6
попробуйте применить алгоритм перебора делителей
avg93
61 / 61 / 10
Регистрация: 11.12.2009
Сообщений: 248
Завершенные тесты: 3
15.07.2014, 17:58     Найти делители "длинного" числа #7
Цитата Сообщение от movielucky Посмотреть сообщение
Дано число 12 тыс. символов. Необходимо найти все его делители. Подскажите как делать. Обязательно ли использовать длинную арифметику?
А как без длинной арифметики тут? Нужны алгоритмы деления длинных чисел.
dogg12
 Аватар для dogg12
59 / 25 / 6
Регистрация: 21.02.2011
Сообщений: 571
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
3020 / 1676 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
15.07.2014, 19:35     Найти делители "длинного" числа #10
dogg12, я вам признателен, что вы процитировали мою программу, но это решение задачи разделить одно длинное число на другое. В данной задаче делений гораздо больше, поэтому она по скорости не подойдет.
dogg12
 Аватар для dogg12
59 / 25 / 6
Регистрация: 21.02.2011
Сообщений: 571
15.07.2014, 19:50     Найти делители "длинного" числа #11
Можно попробовать перейти к двоичной арифметике, как писали выше для деления "в столбик", т.к. алгоритм при таком подходе упрощается.
Sergio Leone
2453 / 1098 / 402
Регистрация: 07.06.2014
Сообщений: 3,259
15.07.2014, 22:54     Найти делители "длинного" числа #12
dogg12, Вы ещё не поняли, в чём затык?
Делители нужно искать в цикле, да?
Попробуйте, для начала,организовать цикл, ну, скажем, до сектилиона.
Напоминаю, что секстиллион это http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{21} (см.вики)
т.е. это число 1000000000000000000000

а теперь допишите ноликов ещё примерно 5 тысяч штук. И подумайте, сколько будем выполняться такой цикл.
dogg12
 Аватар для dogg12
59 / 25 / 6
Регистрация: 21.02.2011
Сообщений: 571
15.07.2014, 23:15     Найти делители "длинного" числа #13
Я понял, но смотрите, у меня такая мысль: будем выполнять деление в столбик.
Переведем числа в двоичную систему.
Сдвигаем делитель влево до тех пор, пока старший бит не станет 1, запоминаем количество сдвигов.
Повторяем столько раз, сколько было сдвигов.
Если делитель (модифицированный) меньше делимого, то вычитаем его из делимого, очередной бит ответа — 1
иначе очередной бит ответа — 0.
Сдвигаем делитель вправо.
Если нет возможности перейти к двоичной арифметике, алгоритм усложнится, потому что на каждом шаге основного цикла надо будет не просто сравнивать делимое с делителем, а вычислять очередную цифру ответа. Для десятичных чисел сдвиг влево — это дополнение делителя справа нулем.
Я не спорю, есть и более скоростные алгоритмы, которые основаны на обработке не одного бита за раз, а сразу группы бит (2, 4, 8), но они сложнее.
Sergio Leone
2453 / 1098 / 402
Регистрация: 07.06.2014
Сообщений: 3,259
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
59 / 25 / 6
Регистрация: 21.02.2011
Сообщений: 571
15.07.2014, 23:26     Найти делители "длинного" числа #15
Тогда подобный вопрос должен стоять явно не в разделе для начинающих)
Sergio Leone
2453 / 1098 / 402
Регистрация: 07.06.2014
Сообщений: 3,259
15.07.2014, 23:30     Найти делители "длинного" числа #16
Цитата Сообщение от dogg12 Посмотреть сообщение
Тогда подобный вопрос должен стоять явно не в разделе для начинающих)
Так автор этого вопроса явно не видит в нём никаких проблем


кстати, он создал дублирующую тему в разделе Java. Ему неважно, на C++ ему напишут программу или на Java. Главное, чтобы она нашла все делители его числа. Он и не подозревает, что скорее наше солнце погаснет, чем программа досчитает до конца.
dogg12
 Аватар для dogg12
59 / 25 / 6
Регистрация: 21.02.2011
Сообщений: 571
15.07.2014, 23:37     Найти делители "длинного" числа #17
Это у нас с вами "простые компьютеры", может человек работает в каком-нибудь супер-пупер мощном вычислительным центре, где большое количество навороченных ЭВМ справятся с такой задачей. Обычно подобные вопросы в таких местах и решают. Люди в НИИ работают над этим годами, а тут на форуме спрашивают... Человечество прогрессирует так сказать)
Psilon
Master of Orion
 Аватар для Psilon
5763 / 4711 / 622
Регистрация: 10.07.2011
Сообщений: 14,188
Записей в блоге: 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
2307 / 1933 / 192
Регистрация: 03.07.2012
Сообщений: 6,922
Записей в блоге: 1
16.07.2014, 18:10     Найти делители "длинного" числа #19
Ищи простые делители с кратностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 18:19     Найти делители "длинного" числа
Еще ссылки по теме:

Найти слово, начинающееся буквой "а" и оканчивающееся буквой "я" C++
C++ Многократное "длинное" деление (длинного на короткое)
Класс "Комплексные числа". Отсортировать массив по возрастанию модуля комплексного числа C++
C++ Найти делители натурального числа
Функции: для каждого числа последовательности найти количество цифр "5" C++

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

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

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