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

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

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

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

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

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

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

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

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

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

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

Ввести в программу строку (числа, латиница), считать только числа, записать числа в массив - C++
Нужна помощь! Срочно! Нужно ввести в программу строку (числа, латиница), считать только числа, записать числа в массив. Помогите,...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 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
Сообщений: 726
23.04.2013, 18:49 #3
решето Эратосфена не нужно при любой разумной реализации этого алгоритма.

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

Добавлено через 7 минут
хотя да... не подумал. просеивание по простым будет очевидно быстрее...)
но делать тест на простоту в программе глуповато на мой взгляд. сделайте прекалк, а потом факторизуйте по заранее готовому массиву простых чисел.
diagon
Higher
1929 / 1195 / 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
Сообщений: 726
23.04.2013, 18:51 #5
асимптотика понижается, так как нет необходимости делать решето в программе.
diagon
Higher
1929 / 1195 / 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
Сообщений: 726
23.04.2013, 18:59 #7
интересно... откуда такая оценка?
diagon
Higher
1929 / 1195 / 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
Сообщений: 726
23.04.2013, 19:06 #9
ок, сп.
думаю, такая сложность зайдет.
осталось выяснить, все ли понятно автору темы...)
dr.curse
388 / 344 / 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
Сообщений: 726
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
388 / 344 / 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)) которое не жрёт памяти
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2013, 22:23
Привет! Вот еще темы с ответами:

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

Дан файл F, компонентами которого являются целые числа. Получить в файле G все нечетные числа, входящие в файл F. Числа в файле G должны следовать - C++
Помогите доздать с++) вот задание: Дан файл F, компонентами которого являются целые числа. Получить в файле G все нечетные числа, входящие ...

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.04.2013, 22:23
Ответ Создать тему
Опции темы

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