Здравствуйте, Pushkin, Вы писали:
P>Сколькими способами 3600 можно разбить на произведение двух сомножителей?
P>PS P>1*3600 не считается, 10*360 и 360*10 считается за одно
P>PPS P>Ну вы поняли ... хоцца формулу для общего случая
Халява. Счиатем делители. Пусть a(n) — кол-во простых чисел n в разложении числа на простые делители.
Если число n не простое, то a(n)=0.
Считаем производение по (n=2..N: a(n+1)).
Это кол-во неэлементарных делителей. Число пар равно половине (округление вверх).
Причина этого удивительного явления очевидна и ее осознвние оставляется как самостоятельно упражнение.
Здравствуйте, Pushkin, Вы писали:
P>Сколькими способами 3600 можно разбить на произведение двух сомножителей?
P>PS P>1*3600 не считается, 10*360 и 360*10 считается за одно
P>PPS P>Ну вы поняли ... хоцца формулу для общего случая
Все весьма просто. Наше число N разлагается в произведение простых множителей:
N = p1^n1 * p2^n2 * ... * pm^nm
Тогда по набору коэффициентов i1...im получим
a = p1^i1 * p2^i2 * ... * pm^im
b = N / a
N = a*b
Таких различных а набирается ((n1+1)*(n2+1)*...(nm+1)) штук. Для учета симметричных случаев поделим это число на два и вычтем единицу для тривиального разложения.
Таким образом, разложений числа будет ((n1+1)*(n2+1)*...(nm+1))/2 — 1
Здравствуйте, Pushkin, Вы писали:
P>Сколькими способами 3600 можно разбить на произведение двух сомножителей?
P>PS P>1*3600 не считается, 10*360 и 360*10 считается за одно
P>PPS P>Ну вы поняли ... хоцца формулу для общего случая
Да, ребята...голыми руками вас не возьмёшь...
Я всё-таки приведу формулу
(n1+1)*(n2+1)*...*(nk+1)/2
Здесь nk — степени простыхо множителей в разложении, а деление с округлением вниз (как в Си)
Для 3600=2^4*3^2*5^2
(4+1)*(2+1)*(2+1)/2=45/2=22
Ну раз вы такие умные, скажите, сколько разложений на ТРИ множителя?
(Различающиеся порядком считаем за одно)
И сколько ВСЕГО разложений (с любым количеством сомножителей)?
Здравствуйте, m.a.g., Вы писали:
MAG>Таких различных а набирается ((n1+1)*(n2+1)*...(nm+1)) штук. Для учета симметричных случаев поделим это число на два и вычтем единицу для тривиального разложения.
MAG>Таким образом, разложений числа будет ((n1+1)*(n2+1)*...(nm+1))/2 — 1
Для N=K^2 нужно округлять в большую сторону (поскольку разложение N=K*K будет сосчитано 1/2 раза, а должно быть 2/2).
P>Ну раз вы такие умные, скажите, сколько разложений на ТРИ множителя? P>(Различающиеся порядком считаем за одно) P>И сколько ВСЕГО разложений (с любым количеством сомножителей)? P>
Если я правильно понимаю, то столько же сколько и всевозможных разбиений в n — элементном множестве, где n — число простых делителей(с повторами), а это числа Стирлинга(вроде) и хорошей формулы для них нет. Только рекуррентная.