Por supuesto, lo primero que debe hacer es encontrar la factorización prima del número, como dijo el glowcoder.Dicen
n = p^a * q^b * r^c * ...
Entonces
- encuentran las particiones multiplicativos de
m = n/p^a
- para
0 <= k <= a, encontrar las particiones multiplicativos de p^k, que es equivalente a encontrar las particiones aditivos de k
- para cada multiplicativo partición de
m, encuentre todas las formas distintas de distribuir a-k factores p entre los factores
- combinar los resultados de 2. y 3.
Es conveniente para el tratamiento de las particiones multiplicativos como listas (o conjuntos) de (divisor, multiplicidad) pares para evitar la producción de duplicados.
He escrito el código en Haskell, porque es la más conveniente y concisa de las lenguas que conozco para este tipo de cosas:
module MultiPart (multiplicativePartitions) where
import Data.List (sort)
import Math.NumberTheory.Primes (factorise)
import Control.Arrow (first)
multiplicativePartitions :: Integer -> [[Integer]]
multiplicativePartitions n
| n < 1 = []
| n == 1 = [[]]
| otherwise = map ((>>= uncurry (flip replicate)) . sort) . pfPartitions $ factorise n
additivePartitions :: Int -> [[(Int,Int)]]
additivePartitions 0 = [[]]
additivePartitions n
| n < 0 = []
| otherwise = aParts n n
where
aParts :: Int -> Int -> [[(Int,Int)]]
aParts 0 _ = [[]]
aParts 1 m = [[(1,m)]]
aParts k m = withK ++ aParts (k-1) m
where
withK = do
let q = m `quot` k
j <- [q,q-1 .. 1]
[(k,j):prt | let r = m - j*k, prt <- aParts (min (k-1) r) r]
countedPartitions :: Int -> Int -> [[(Int,Int)]]
countedPartitions 0 count = [[(0,count)]]
countedPartitions quant count = cbParts quant quant count
where
prep _ 0 = id
prep m j = ((m,j):)
cbParts :: Int -> Int -> Int -> [[(Int,Int)]]
cbParts q 0 c
| q == 0 = if c == 0 then [[]] else [[(0,c)]]
| otherwise = error "Oops"
cbParts q 1 c
| c < q = [] -- should never happen
| c == q = [[(1,c)]]
| otherwise = [[(1,q),(0,c-q)]]
cbParts q m c = do
let lo = max 0 $ q - c*(m-1)
hi = q `quot` m
j <- [lo .. hi]
let r = q - j*m
m' = min (m-1) r
map (prep m j) $ cbParts r m' (c-j)
primePowerPartitions :: Integer -> Int -> [[(Integer,Int)]]
primePowerPartitions p e = map (map (first (p^))) $ additivePartitions e
distOne :: Integer -> Int -> Integer -> Int -> [[(Integer,Int)]]
distOne _ 0 d k = [[(d,k)]]
distOne p e d k = do
cap <- countedPartitions e k
return $ [(p^i*d,m) | (i,m) <- cap]
distribute :: Integer -> Int -> [(Integer,Int)] -> [[(Integer,Int)]]
distribute _ 0 xs = [xs]
distribute p e [(d,k)] = distOne p e d k
distribute p e ((d,k):dks) = do
j <- [0 .. e]
dps <- distOne p j d k
ys <- distribute p (e-j) dks
return $ dps ++ ys
distribute _ _ [] = []
pfPartitions :: [(Integer,Int)] -> [[(Integer,Int)]]
pfPartitions [] = [[]]
pfPartitions [(p,e)] = primePowerPartitions p e
pfPartitions ((p,e):pps) = do
cop <- pfPartitions pps
k <- [0 .. e]
ppp <- primePowerPartitions p k
mix <- distribute p (e-k) cop
return (ppp ++ mix)
no es especialmente optimizado, pero hace el trabajo.
Algunas veces y los resultados:
Prelude MultiPart> length $ multiplicativePartitions $ 10^10
59521
(0.03 secs, 53535264 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ 10^11
151958
(0.11 secs, 125850200 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ 10^12
379693
(0.26 secs, 296844616 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 10]
70520
(0.07 secs, 72786128 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 11]
425240
(0.36 secs, 460094808 bytes)
Prelude MultiPart> length $ multiplicativePartitions $ product [2 .. 12]
2787810
(2.06 secs, 2572962320 bytes)
El 10^k son, por supuesto, sobre todo fácil porque sólo hay dos números primos implicados (pero los números sin cuadrados son todavía más fácil), los factoriales consiguen lenta antes. Creo que mediante una organización cuidadosa del orden y la elección de mejores estructuras de datos que las listas, hay bastante que ganar (probablemente uno debería ordenar los factores primos por exponente, pero no sé si uno debe comenzar con los exponentes más altos o el más bajo).
Con votos cercanos, idealmente debería haber algún tipo de explicación de por qué cree que esto debe cerrarse, para que el OP pueda rectificar sus errores (si corresponde). ¿Puede el votante cercano solitario hablar por favor? – TCSGrad
Votos cerrados sin ninguna explicación, ¡siempre los amé! – TCSGrad
Eché un voto de cerca por error. Mis disculpas. –