Ovviamente, la prima cosa da fare è trovare la fattorizzazione principale del numero, come indicato da glowcoder.Dire
n = p^a * q^b * r^c * ...
Poi
- trovare le partizioni moltiplicativi di
m = n/p^a
- per
0 <= k <= a, trovare le partizioni moltiplicativi di p^k, che è equivalente a trovare le partizioni additivi di k
- per ogni moltiplicativo partizione di
m, trovare tutti modi distinti per distribuire a-k fattori p tra i fattori
- combinano risultati di 2. e 3.
È conveniente trattare le partizioni moltiplicativi come liste (o set) di (divisore) molteplicità coppie per evitare di produrre duplicati.
ho scritto il codice in Haskell, perché è il più conveniente e conciso delle lingue che conosco per questo genere di cose:
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)
Non è particolarmente ottimizzato, ma fa il lavoro.
Alcune tempi e risultati:
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)
La 10^k sono ovviamente particolarmente facile perché ci sono solo due numeri primi coinvolti (ma i numeri sono ancora più facili senza quadrati), i fattoriali ottenere lento in precedenza. Credo che da un'attenta organizzazione dell'ordine e la scelta di migliori strutture di dati di elenchi, c'è un bel po 'da guadagnare (probabilmente si dovrebbe ordinare i fattori primi di esponente, ma non so se si debba iniziare con i più alti esponenti o il più basso).
Con stretti voti, ci idealmente dovrebbe essere una sorta di una spiegazione sul motivo per cui si pensa che questo deve essere chiuso, in modo che l'OP può rettificare le sue/suoi errori (se presente). L'elettore chiuso da solo può parlare per favore? – TCSGrad
Chiusura ravvicinata senza spiegazioni - sempre amate quelle! – TCSGrad
Ho espresso un voto ravvicinato per errore. Mie scuse. –