直接按升序枚举数字的因子而不进行排序？

一尘不染

直接按升序枚举数字的因子而不进行排序？

algorithm

是否有一种高效的算法可以对 n 的因子进行升序排序而不进行排序？“有效”是指：

该算法通过从 n 的素幂分解开始避免对除数的强力搜索。
该算法的运行时间复杂度是O（ d log 2 d ）或更好，其中 d 是 n 的除数。
该算法的空间复杂度为O（ d ）。
该算法避免了排序操作。也就是说，因子是 按顺序 生成的，而不是无序生成的，然后进行排序。尽管使用简单的递归方法进行枚举，然后排序为O（ d log 2 d ），但是与排序有关的所有内存访问的成本都非常难看。

一个简单的例子是 n = 360 =2³×3²×5，它具有 d =
24个因子：{1，2，3，4，5，6，8，9，9，10，12，15，18，20，24， 30、36、40、45、60、72、90、120、180、360}。

一个更严重的例子是 n = 278282512406132373381723386382308832000
=2⁸×3⁴×5³×7²×11²×13²×17×19×23×29×31×37×41×43×47×53×59×61×67×71×73 ×79，它具有 d
= 318504960个因子（显然太多了，无法在此处列出！）。顺便说一下，这个数字具有最多2 ^ 128个因素中的最大数目。

我可以保证几周前看到了有关这种算法的描述，并附有示例代码，但现在似乎找不到任何地方。它使用了一些魔术技巧，可以在每个主要因子的输出列表中维护祖细胞索引列表。（更新：我将因子生成与汉明数混淆，后者的运算类似。）

更新资料

我最终使用了一种在运行时为O（ d ）的解决方案，它具有极低的内存开销，可以就地创建O（ d
）输出，并且比我所知道的任何其他方法都快得多。我已将此解决方案发布为带有C源代码的答案。它是另一位贡献者Will
Ness在Haskell提出的精美算法的经过严格优化的简化版本。我选择了威尔的答案作为可接受的答案，因为它提供了一个非常优雅的解决方案，可以满足最初陈述的所有要求。

阅读 205

2020-07-28

共1个答案

一尘不染

我们可以合并产生的倍数流，因此一开始就没有重复项。

从list开始[1]，对于每个唯一的素因子p，我们将列表乘以p迭代k次数（k的倍数p）乘以得到k新列表，并将它们与该传入列表合并在一起。

在Haskell，

ordfactors n =          --   <----------------------<---<---<-----\
  foldr g [1]           -- g (19,1) (g (7,1) (g (3,2) (g (2,3) [1])))
    . reverse           -- [(19,1),(7,1),(3,2),(2,3)]              ^
    . primePowers       -- [(2,3),(3,2),(7,1),(19,1)]              |
    $ n                 -- 9576                    --->--->--->----/
       where
         g (p,k) xs = mergeAsTree 
                        . take (k+1)          -- take 3 [a,b,c,d..] = [a,b,c]
                        . iterate (map (p*))  -- iterate f x = [x, f x, f(f x),...]
                        $ xs

{-  g (2,3) [1] = let a0 = [1]        
                      a1 = map (2*) a0               -- [2]
                      a2 = map (2*) a1               -- [4]
                      a3 = map (2*) a2               -- [8]
                  in mergeAsTree [ a0, a1, a2, a3 ]  -- xs2 = [1,2,4,8]

    g (3,2) xs2 = let b0 = xs2                       -- [1,2,4,8]
                      b1 = map (3*) b0               -- [3,6,12,24]
                      b2 = map (3*) b1               -- [9,18,36,72]
                  in mergeAsTree [ b0, b1, b2 ]      -- xs3 = [1,2,3,4,6,8,9,12,...]

    g (7,1) xs3 = mergeAsTree [ xs3, map (7*) xs3 ]  -- xs4 = [1,2,3,4,6,7,8,9,...]

    g (19,1) xs4 = mergeAsTree [ xs4, map (19*) xs4 ]  
-}
mergeAsTree xs   = foldi merge [] xs    -- [a,b]     --> merge a b
                                        -- [a,b,c,d] --> merge (merge a b) (merge c d)
foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))
pairs f (x:y:t)  = f x y : pairs f t
pairs _ t        = t

foldi以类似于树的方式将二进制merges（假定要合并的流中没有重复项，以进行简化的操作）以提高速度；而foldr以线性方式工作。

primePowers n | n > 1 =           -- 9576 => [(2,3),(3,2),(7,1),(19,1)]
  map (\xs -> (head xs,length xs)) --                                ^
    . group                       -- [[2,2,2],[3,3],[7],[19]]        |
    . factorize                   -- [2,2,2,3,3,7,19]                |
    $ n                           -- 9576             --->--->--->---/

group是将列表中的相邻等式分组在一起的标准函数，并且factorize是一种众所周知的试算算法，它以不降序生成数字的质因数：

factorize n | n > 1 = go n (2:[3,5..])   -- 9576 = 2*2*2*3*3*7*19
   where                                 -- produce prime factors only
     go n (d:t)
        | d*d > n    = [n]
        | r == 0     =  d : go q (d:t)
        | otherwise  =      go n t
            where 
              (q,r)  = quotRem n d
factorize _ = []

(.)是一个函数组合运算符，将其右边的自变量函数的输出作为输入链接到其左边的输入。它（和$）可以大声读出为“ of”。

2020-07-28