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

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

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

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

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

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

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

Дан файл F, компонентами которого являются целые числа. Получить в файле G все нечетные числа, входящие в файл F. Числа в файле G должны следовать C++
C++ От данного числа N вычтем сумму цифр этого числа, от полученного числа опять вычтем сумму цифр и т.д. до тех пор, пока число положительно
Подсчет числа четных цифр, используемых в написании N-значного числа М (функции) C++
C++ Факторизация методом NFS
C++ Дано два числа А и В (А<В). Вывести в порядке увеличения все целые числа
C++ Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел?
Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
23.04.2013, 18:33     Факторизация числа #2
Цитата Сообщение от Ternsip Посмотреть сообщение
10^12
Цитата Сообщение от Ternsip Посмотреть сообщение
Время на работу программы : 1 сек.
На таких ограничениях будет достаточно брутфорса - просто пускаете решето эратосфена до корня из n, и для каждого найденного простого числа проверяете n на делимость на это простое число.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
23.04.2013, 18:49     Факторизация числа #3
решето Эратосфена не нужно при любой разумной реализации этого алгоритма.

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

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

Практически все быстрые алгоритмы рассчитаны на более крупные числа, а для таких ограничений простой перебор отработает за милисекунды.
Но если интересуют реализации для действительно больших чисел(от 100 десятичных знаков и выше), то можете посмотреть в сторону YAFU.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
23.04.2013, 18:51     Факторизация числа #5
асимптотика понижается, так как нет необходимости делать решето в программе.
diagon
Higher
1921 / 1187 / 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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
23.04.2013, 18:59     Факторизация числа #7
интересно... откуда такая оценка?
diagon
Higher
1921 / 1187 / 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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
23.04.2013, 19:06     Факторизация числа #9
ок, сп.
думаю, такая сложность зайдет.
осталось выяснить, все ли понятно автору темы...)
dr.curse
386 / 342 / 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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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
386 / 342 / 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
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.04.2013, 22:25     Факторизация числа #16
Цитата Сообщение от Ternsip Посмотреть сообщение
aram_gyumri, да, как бы проблема решена уже, вон, я написал решение O(sqrt(n)) которое не жрёт памяти
да увидел что решена, просто сказал так сказать на будущее
и еще откуда задача?
_Ivana
2822 / 1647 / 142
Регистрация: 01.03.2013
Сообщений: 4,699
Записей в блоге: 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 - натуральное число
. Для меня остается загадкой, как ТС, утверждавший что прочитал весь инет по данному вопросу, написал такой алгоритм.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2013, 07:42     Факторизация числа
Еще ссылки по теме:

C++ Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми
Даны два числа. Если квадратный корень из второго числа меньше первого числа, то увличить второе число в пять раз с++ C++
Факторизация методом Шнорра-Ленстры C++
Ввести в программу строку (числа, латиница), считать только числа, записать числа в массив C++
C++ Найти числа-близнецы: простые числа разность между которыми равна 2

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2013, 07:42     Факторизация числа #18
Цитата Сообщение от _Ivana Посмотреть сообщение
Для меня остается загадкой, как ТС, утверждавший что прочитал весь инет по данному вопросу, написал такой алгоритм.

Не по теме:

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

Yandex
Объявления
29.12.2013, 07:42     Факторизация числа
Ответ Создать тему
Опции темы

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