直接按升序枚举数字的因子而不进行排序？ [英] Enumerate factors of a number directly in ascending order without sorting?

问题描述

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

1. 该算法通过从素数幂分解开始避免了对除数的暴力搜索。 n 的值。




2. 该算法的运行时复杂度为O（ d log² d ）或更好，其中 d 是 n 的除数。




3. 该算法的空间复杂度为O（ d ）。




4. 该算法避免了排序操作。也就是说，因子是按顺序产生的，而不是顺序产生的，然后进行排序。尽管使用简单的递归方法进行枚举，然后排序为O（ d log2 d ），但是与排序有关的所有内存访问的开销都非常难看。

一个简单的例子是 n = 360 =2³×3²×5，其中 d = 24个因素：{1，2，3，4，5，6，8，9，10，12，15，18，20，24，30，36，40，45，60，72， 90、120、180、360}。 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提出的精美算法的经过严格优化的简化版本。我选择了Will的答案作为可接受的答案，因为它提供了一个非常优雅的解决方案，可以满足最初提出的所有要求。

解决方案

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

从列表 [1] 开始，对于每个唯一的素数 p ，我们将列表乘以 p 乘以 k 倍（其中 k 是 p 的多样性），以获取 k 个新列表，并将其与该传入列表。

在Haskell中，

  ordfactors n =-< ----------------------< ---< ---< ----- \ 
文件夹g [1]-g（19,1）（g（7,1）（g（3,2）（g（2,3）[1]）））
。反向-[[（19,1），（7,1），（3,2），（2,3）] ^ 
。 primePowers-[（2,3），（3,2），（7,1），（19,1）] | 
 $ n-9576 ---> ---> ---> ---- / 
其中
g（p，k）xs = mergeAsTree 
 。取（k + 1）-取3 [a，b，c，d ..] = [a，b，c] 
。迭代（map（p *））-迭代fx = [x，fx，f（fx），...] 
 $ xs 
 
 {-g（2,3）[ 1] =让a0 = [1] 
 a1 =地图（2 *）a0-[2] 
 a2 =地图（2 *）a1-[4] 
 a3 =地图（2 *）a2-[8] mergeAsTree中的
 [a0，a1，a2，a3]-xs2 = [1,2,4,8] 
 
g（3,2 ）xs2 =让b0 = xs2-[1,2,4,8] 
 b1 =地图（3 *）b0-[3,6,12,24] 
 b2 =地图（3 *）b1-mergeAsTree [b0，b1，b2]中的[9,18,36,72] 
-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，地图（19 *）xs4] 
-} 
 mergeAsTree xs = foldi merge [] xs-[ a，b]->合并a b 
-[a，b，c，d]->合并（合并ab）（合并cd）
 foldi fz [] = z 
 foldi fz（x：xs）= fx（foldi fz（pairs f xs））
 Pairs f（x： y：t）= fxy：对ft 
对_ t = t 
  

foldi 排列二进制 合并 s （为了简化操作，假定要合并的流中没有重复项）以树状方式以提高速度；而 foldr 以线性方式工作。

  primePowers n | n> 1 =-9576 => [（2,3），（3,2），（7,1），（19,1）] 
映射（\xs->（head xs，length xs））-^ 
。组-[[2,2,2]，[3,3]，[7]，[19]] | 
。分解-[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 
其中-仅产生素因子
 go n（ d：t）
 | d * d> n = [n] 
 | r == 0 = d：转到q（d：t）
 |否则=去nt 
，其中
（q，r）= Rem nd 
分解_ = [] 
  

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

Is there an efficient algorithm to enumerate the factors of a number n, in ascending order, without sorting? By "efficient" I mean:

1. The algorithm avoids a brute-force search for divisors by starting with the prime-power factorization of n.

2. The runtime complexity of the algorithm is O(d log₂ d) or better, where d is the divisor count of n.

3. The spatial complexity of the algorithm is O(d).

4. The algorithm avoids a sort operation. That is, the factors are produced in order rather than produced out of order and sorted afterward. Although enumerating using a simple recursive approach and then sorting is O(d log₂ d), there is a very ugly cost for all the memory accesses involved in sorting.

A trivial example is n = 360 = 2³ × 3² × 5, which has d=24 factors: { 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360 }.

A more serious example is n = 278282512406132373381723386382308832000 = 2⁸ × 3⁴ × 5³ × 7² × 11² × 13² × 17 × 19 × 23 × 29 × 31 × 37 × 41 × 43 × 47 × 53 × 59 × 61 × 67 × 71 × 73 × 79, which has d=318504960 factors (obviously too many to list here!). This number, incidentally, has the greatest number of factors of any number up to 2^128.

I could swear that I saw a description of such algorithm a few weeks ago, with sample code, but now I can't seem to find it anywhere. It used some magic trick of maintaining a list of progenitor indexes in the output list for each prime factor. (Update: I was confusing factor generation with Hamming numbers, which operate similarly.)

Update

I ended up using a solution which is O(d) in runtime, has extremely low memory overhead creating the O(d) output in-place, and is significantly faster than any other method I am aware of. I've posted this solution as answer, with C source code. It is a heavily optimized, simplified version of a beautiful algorithm presented here in Haskell by another contributor, Will Ness. I've selected Will's answer as the accepted answer, as it provided a very elegant solution that matched all the requirements as originally stated.

解决方案

We can merge streams of multiples, produced so there are no duplicates in the first place.

Starting with the list [1], for each unique prime factor p, we multiply the list by p iteratively k times (where k is the multiplicity of p) to get k new lists, and merge them together with that incoming list.

In 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 arranges the binary merges (which presuppose that there's no duplicates in the streams being merged, for streamlined operation) in a tree-like fashion for speed; whereas foldr works in linear fashion.

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 is a standard function that groups adjacent equals in a list together, and factorize is a well-known trial-division algorithm that produces prime factors of a number in non-decreasing order:

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 _ = []

(.) is a functional composition operator, chaining the output of its argument function on its right as input into the one on its left. It (and $) can be read aloud as "of".

这篇关于直接按升序枚举数字的因子而不进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！