Разложение чисел на множители

Школу прогуливал?

Разложение чисел на множители

вас это беспокоит, хотите поговорить об этом? :)

вроде у Шнайера в прикладной криптографии описывается алгоритм. Если погуглить, тоже что-нибудь найдется

man factor + смотри исходники

Как для целого числа n перчислить все его возможные разложения на множители?

Тяжела жизнь забанненого в википедии ...
http://ru.wikipedia.org/wiki/Факторизация_целых_чисел

Берёшь квантовый компьютер и раскладываешь за ~logN.

Разложение числа на множители отличается от разложения на простые множители тем, что оно не единственно.

По ссылке сходить, конечно, слабо?

Факториза́цией натурального числа называется его разложение в произведение простых множителей

2^k

Нет.

Но зачем?

Я думаю, что надо адаптировать алгоритм тот разбиения на слагаемые.

for (int i = 0; i < sqrt(N); ++i)

Дальше сам думай.

Наверное, всё же придётся делать разбиение множества алгоритмом бэктрекинга. Плохо то, что алгоритм экспоненциальный, значит медленный.

За 50$ поделюсь линейным, только тсс - никому.

Меряемся писюками, у кого быстрее :-)

$ time factor 9999999999999997111
9999999999999997111: 9999999999999997111

real    0m4.994s
user    0m4.972s
sys     0m0.004s

Линейный алгоритм получения всех возможных комбинаций множителей заданного числа? Он существует? О_О

Это сарказм? У меня плохо с детектором, так что на всякий случай выше по треду ссылка на википедию, выбирай любой.

Поиск привёл как всегда к книге Кнута. Глава 7.2.1 «Разбиение мультимножеств».

С таблицей значений? К слову в дебиане:

time factor 9999999999999997111
9999999999999997111: 9999999999999997111

real    0m6.517s
user    0m6.464s
sys     0m0.036s
factor (GNU coreutils) 8.13
Copyright (C) 2011 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Paul Rubin.

Кажется я несу чушь.

real	0m0.080s
user	0m0.003s
sys	0m0.002s

Компу 8 лет. Что у тебя за гуано мамонта?

Говно мамонта у тебя вместо мозгов (и у меня вместо ос). Ты бы версии сравнил для начала — где-то в 2011-2012 factor-ng.c смержили в factor.c, делай выводы.

С таблицей значений?

Эвристики разные, скорее всего (make-prime-list.c -> primes.h тоже). Например

$ time factor      123456789123456789123456789123456789123456789123456789  
123456789123456789123456789123456789123456789123456789: 3 3 3 7 11 13 19 757 3607 3803 52579 70541929 14175966169 440334654777631
factor 123456789123456789123456789123456789123456789123456789  0,04s user 0,00s system 97% cpu 0,044 total
$ timeout 5 factor 123456789123456789123456789123456789123456789123456

Меряемся писюками, у кого быстрее :-)

~$ time factor 9999999999999997111
9999999999999997111: 9999999999999997111

real	0m0.001s
user	0m0.000s
sys	0m0.000s

~$ factor --version
factor (GNU coreutils) 8.20
Copyright (C) 2012 Free Software Foundation, Inc.

есть как бы основная теорема арифметики ( о единственности представления числа в виде произведения степеней простых делителей)

F=a**Z*b**Y*c**X*....

где a,b,c, ряд(весь) простых чисел Z,Y,X,.. - в какой степени (т.е максимальное число сколько раз можно последовательно делить начиная с исходного без остатка) этот простой делитель делит данное число F - очевидно что большинство показателей будет нули ( и обычно их(соот простые числа) просто не выписывают))

обрати внимания что такая запись(не нулевые показатели) похожа на позиционую запись.

можеш понять что всякие делители(включая 1 и само число) исходного числа в такой форме имеет на каждой позиции число в диапазоне от нуля до максимальной для даного числа.

т.е общее число делителей(с учётом 1 и самого числа) есть произведение степеней( увеличеных на 1) рекурсивно можно красиво перечислять все делители .

http://www.math.wvu.edu/~mays/Papers/Factorizations.pdf

Я думаю, что надо адаптировать алгоритм тот разбиения на слагаемые.

не подойдет, автор же явно написал:

для целого числа n перечислить все его возможные разложения на множители?

нужно адаптировать алгоритм разбиения на все возможные слагаемые

итить, когда уже в этой теме дойдут до таблицы умножения?

Дональд Кнут

вот тебе пример, а долго это или нет - сам решай:

Sat Feb 16 20:49:04 2013  factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits)
Sun Feb 17 06:37:54 2013  prp50 factor: 37975227936943673922808872755445627854565536638199
Sun Feb 17 06:37:54 2013  prp50 factor: 40094690950920881030683735292761468389214899724061
Sun Feb 17 06:37:54 2013  elapsed time 09:48:50

а вот повторно с учётом уже сохранённого «решета»:

Sun Feb 17 10:07:02 2013  factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits)
Sun Feb 17 10:07:45 2013  prp50 factor: 37975227936943673922808872755445627854565536638199
Sun Feb 17 10:07:45 2013  prp50 factor: 40094690950920881030683735292761468389214899724061
Sun Feb 17 10:07:45 2013  elapsed time 00:00:43

ТС не каноническое разложение нужно, а мультипликативные композиции, например

12 = {{2, 2, 3}, {2, 3, 2}, {2, 6}, {3, 2, 2}, {3, 4}, {4, 3}, {6, 2}, {12}}

или без учёта порядка

12 = {{3, 2, 2}, {4, 3}, {6, 2}, {12}}

т.е. мультипликативные разбиения, по аналогии с аддитивными разбиениями (которые чаще встречаются). Про то как считать - http://www.math.wvu.edu/~mays/Papers/Factorizations.pdf, ещё на SO был вопрос - http://stackoverflow.com/q/8558292/1337941 - если каноническое разложение уже есть, то всё сводится к построению всех разбиений множества, можно нагуглить разные алгоритмы, в том числе у Кнута.

Иначе говоря, в данном кольце для данного элемента x может быть множество наборов элементов произведение которых = x, вне зависимости от канонического разложения, которое, конечно, одно (в UFD). Вот такое множество наборов для данного x \in N \sub Z нужно найти.

Изящный алгоритм больше не нужен, задача уже решена варварски.

Делаете функцию, в ней цикл i от 2 до sqrt(n), в нем рекурсивный вызов этой функции для (n % i) (под % я понимаю целочисленное деление), если нет остатка

Что может быть изящней рекурсии?

Так мы получили бы многие разложения многократно. Например, (8,4) и (4,8).

Ну да, потом надо уникальные выделить