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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.71
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

Факторизация числа - C++

23.04.2013, 16:56. Просмотров 5892. Ответов 18
Метки нет (Все метки)

Известно, что факторизация числа -- это разложение на простые множители. Так же известно, что любое число можно факторизовать.
Нужно факторизовать число N (1<N<=10^12). Время на работу программы : 1 сек.
Мне бы очень хотелось увидеть аккуратный алгоритм. Видимо, такой алгоритм будет основан на вероятностных тестах, для определения простого числа.
Если есть готовый код или кто-то может написать, а не ссылаться на другие источники, то прошу ответить мне.
Да, я знаю тема сложная из раздела целочисленных алгоритмов. Подчеркну, что мне не интересны чужие статьи, т.к. теоретически я уже ознакомлен с данной темой и грубый, не красивый код я уже набросал.

Хочу добавить, что какие-либо математические библиотеки, связанные с данной темой, меня очень интересуют.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2013, 16:56     Факторизация числа
Посмотрите здесь:

Факторизация методом NFS - C++
у кого есть какие нибудь исходники для факторизации методом решета числового поля? самому что то пока даже доступный алгоритм не...

Факторизация методом Шнорра-Ленстры - C++
Собственно курсач по этому методу. В рунете информации по нему практически нет, но нашёл в какой-то иностранной книге коротенький параграф...

Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел? - C++
Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел?

Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми - C++
Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми. ...

Факторизация числа - Математика
Здравствуйте! Помогите пожалуйста произвести факторизацию числа 0x5f0b1630eec4db90cc7f Возможно ли это сделать с помощью...

Факторизация числа - Pascal ABC
Разложить целое число на множители с помощью алгоритма Полларда. Проверить является ли множитель простым числом, если нет, то выполнить...

ро-метод Полларда (факторизация числа) - Delphi
Доброго времени суток! Необходимо написать ро-алгоритм Полларда. Взял Кнута с его &quot;Искусство программирования&quot;, реализовал. Но программа...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.04.2013, 18:33     Факторизация числа #2
Цитата Сообщение от Ternsip Посмотреть сообщение
10^12
Цитата Сообщение от Ternsip Посмотреть сообщение
Время на работу программы : 1 сек.
На таких ограничениях будет достаточно брутфорса - просто пускаете решето эратосфена до корня из n, и для каждого найденного простого числа проверяете n на делимость на это простое число.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
23.04.2013, 18:49     Факторизация числа #3
решето Эратосфена не нужно при любой разумной реализации этого алгоритма.

Добавлено через 2 минуты
классическая реализация имеет сложность порядка sqrt(N). но коэффициент (из-за частого деления) там плохой. теоретически мне кажется возможным, чтобы этот алгоритм факторизовал до 10^12.

Добавлено через 7 минут
хотя да... не подумал. просеивание по простым будет очевидно быстрее...)
но делать тест на простоту в программе глуповато на мой взгляд. сделайте прекалк, а потом факторизуйте по заранее готовому массиву простых чисел.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.04.2013, 18:49     Факторизация числа #4
Цитата Сообщение от salam Посмотреть сообщение
решето Эратосфена не нужно при любой разумной реализации этого алгоритма.
Если проверять на делимость на каждое нечетное число до корня из n, то действительно
коэффициент (из-за частого деления) там плохой.
Особенно если программа заточена под 32 бита (т.к. n - 64 битное число).
Решето Эратосфена позволяет избавится от множества ненужных делений. Ассимптотика, правда, чуть-чуть повышается, но зато константа сильно падает.

Практически все быстрые алгоритмы рассчитаны на более крупные числа, а для таких ограничений простой перебор отработает за милисекунды.
Но если интересуют реализации для действительно больших чисел(от 100 десятичных знаков и выше), то можете посмотреть в сторону YAFU.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
23.04.2013, 18:51     Факторизация числа #5
асимптотика понижается, так как нет необходимости делать решето в программе.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.04.2013, 18:57     Факторизация числа #6
Цитата Сообщение от salam Посмотреть сообщение
асимптотика понижается, так как нет необходимости делать решето в программе.
Потребуется захардкодить около 70к простых чисел. А это немало. Но да, тогда ассимптотика снизится до http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\frac{\sqrt{n}}{\log\sqrt{n}})
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
23.04.2013, 18:59     Факторизация числа #7
интересно... откуда такая оценка?
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.04.2013, 19:03     Факторизация числа #8
Цитата Сообщение от salam Посмотреть сообщение
интересно... откуда такая оценка?
Я там лишний log случайно вставил :)
Для факторизации потребуется проверить n на делимость на все простые числа до корня из n. Количество простых чисел до k примерно равно http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{k}{\log{k}}.
Подставляем вместо k корень из n.
???
профит
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
23.04.2013, 19:06     Факторизация числа #9
ок, сп.
думаю, такая сложность зайдет.
осталось выяснить, все ли понятно автору темы...)
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.04.2013, 19:17     Факторизация числа #10
вот тут есть и другие алгоритмы факторизации http://e-maxx.ru/algo/factorization
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.04.2013, 19:33  [ТС]     Факторизация числа #11
Друзья, простите, забыл сказать, что памяти выделяется слишком мало, чтобы хватило на решето, даже если использовать битовое сжатие, которое вшито в vector <bool>.

Добавлено через 45 секунд
aram_gyumri, сайт e-maxx я прекрасно знаю и приведённые там статьи я уже прочитал.

Добавлено через 2 минуты
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
23.04.2013, 19:46     Факторизация числа #12
поэтому в том числе лучше использовать прекалк.
если вам принципиально "чисто" все написать, то реализуйте классику.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.04.2013, 20:24  [ТС]     Факторизация числа #13
Вот написал. Памяти жрёт ровно на хранение ответа.
Выводит простые числа и их степень в разложении.
Всё работает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cin >> n;
vector <pair<int, long long>> ans;
for (long long i = 2; i*i <= n; i++) {
    if (n % i == 0) {
        ans.push_back(make_pair(0, i));
        while (n % i == 0) {
            n /= i;
            ans[ans.size()-1].first--;
        }
    }
}
if (n > 1) {
    ans.push_back(make_pair(-1, n));
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
    printf("%I64d %d\n", ans[i].second, -ans[i].first);
}
Добавлено через 5 минут
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.04.2013, 22:16     Факторизация числа #14
Цитата Сообщение от Ternsip Посмотреть сообщение
Друзья, простите, забыл сказать, что памяти выделяется слишком мало, чтобы хватило на решето, даже если использовать битовое сжатие, которое вшито в vector <bool>.
ну тогда можно использовать блочное решето
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.04.2013, 22:23  [ТС]     Факторизация числа #15
aram_gyumri, да, как бы проблема решена уже, вон, я написал решение O(sqrt(n)) которое не жрёт памяти
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.04.2013, 22:25     Факторизация числа #16
Цитата Сообщение от Ternsip Посмотреть сообщение
aram_gyumri, да, как бы проблема решена уже, вон, я написал решение O(sqrt(n)) которое не жрёт памяти
да увидел что решена, просто сказал так сказать на будущее
и еще откуда задача?
_Ivana
3041 / 1728 / 150
Регистрация: 01.03.2013
Сообщений: 4,906
Записей в блоге: 2
29.12.2013, 00:37     Факторизация числа #17
Простите за некропост, но не могу не прокомментить ))

Вчера мой сын-восьмиклассник в качестве примера освоения собственных типов в Паскале озадачился идеей - написать калькулятор рациональных чисел (в натуральных дробях). Сразу выяснили, что 4 арифметические операции реализуются тривиально, осталось только нормализовать результат - привести к несократимой дроби. Ну я и сказал - придумай сам более-менее эффективный алгоритм, не просто перебор всех натуральных чисел до корня из факторизуемого - это неоптимально, и не перебор всех простых до того же предела - надо иметь длинный массив готовых простых. Сейчас почитал в вики обзор методов факторизации и подумал, что несколько опрометчиво озадачил его этим вопросом...

Результат поиска вывел меня на этот топик и я увидел код... А в нем
C
1
i++
... Простите, но даже мой сын сразу сказал, что проверять четные делители после двойки не имеет смысла, то есть можно только по нечетным скакать, а лучше по простым. А если взглянуть сюда http://ru.wikipedia.org/wiki/%D0%9F%...BB%D0%B5%D0%B9 , то можно и кратные трем пропускать - нехитрой процедурой
представляя делители в формате 6k±1, где k - натуральное число
. Для меня остается загадкой, как ТС, утверждавший что прочитал весь инет по данному вопросу, написал такой алгоритм.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2013, 07:42     Факторизация числа #18
Цитата Сообщение от _Ivana Посмотреть сообщение
Для меня остается загадкой, как ТС, утверждавший что прочитал весь инет по данному вопросу, написал такой алгоритм.

Не по теме:

если внимательно изучить страничку по ссылке, можно увидеть, что когда ТС писал эти сообщения, указанной странички не существовало )

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2017, 11:43     Факторизация числа
Еще ссылки по теме:

Факторизация числа (разложение на множители) - C (СИ)
Привет всем. У меня есть код, который выполняет деление на 2 и выводит ответ. Как можно зациклить его, чтобы на выходе вышел конечный...

Факторизация (раскладывание числа на множители, нахождение их суммы) - PascalABC.NET
Помогите, пожалуйста, написать прогу на Pascal ABC. NET на тему: Факторизация (должна раскладывать число на множители, находить их сумму и...

LU факторизация - Delphi
Доброго времени суток, помогите пожалуйста написать программу решения линейных алгебраических уравнений методом LU факторизации если...

Факторизация по модулям 6 и 4 - Математика
Мною разработана &quot;Методика определения делимости чисел натурального числового ряда и её практическое применение&quot;. Она основана на...

НОК и факторизация - Pascal
Собственно говоря, программы есть, вот только я не знаю, как можно сократить время их работы. 1)Требуется найти НОК двух чисел. Входные...


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

Или воспользуйтесь поиском по форуму:
bedvit
206 / 76 / 11
Регистрация: 20.05.2016
Сообщений: 322
Записей в блоге: 3
24.05.2017, 11:43     Факторизация числа #19
Сам недавно реализовал простенький алгоритм. Хотелось бы понять есть ли реализованные более быстрые на С++ для НЕ распределённого вычисления, для обычного ПК?
Yandex
Объявления
24.05.2017, 11:43     Факторизация числа
Ответ Создать тему
Опции темы

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