直接按升序枚举一个数的因数而不排序? [英] Enumerate factors of a number directly in ascending order without sorting?
问题描述
是否有一种高效的算法可以按升序枚举一个数 n 的因数而不进行排序?我所说的高效"是指:
Is there an efficient algorithm to enumerate the factors of a number n, in ascending order, without sorting? By "efficient" I mean:
该算法从 n 的素数功率因数分解开始，避免了对除数的蛮力搜索.
The algorithm avoids a brute-force search for divisors by starting with the prime-power factorization of n.
算法的运行时复杂度为 O(d log₂ d) 或更好，其中 d 是n.
The runtime complexity of the algorithm is O(d log₂ d) or better, where d is the divisor count of n.
算法的空间复杂度为 O(d).
The spatial complexity of the algorithm is O(d).
该算法避免了排序操作.也就是说，因子是按顺序生成的，而不是乱序生成然后排序.尽管使用简单的递归方法枚举然后排序是 O(d log2 d)，但排序中涉及的所有内存访问成本非常高.
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.
一个简单的例子是 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 }.
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 }.
更严重的例子是n = 278282512406132373381723386382308832000 = 2⁸ × 3⁴ × 5³ × 7² × 11² × 13² × 17 × 19 ×3 ×3 ×3 ×3 ×3 ×3× 59 × 61 × 67 × 71 × 73 × 79，其中有 d=318504960 个因子(显然太多了，无法在此列出！).顺便说一下，这个数是最多 2^128 的任何数中因数最多的数.
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.)
我最终使用了一个运行时 O(d) 的解决方案，具有极低的内存开销，就地创建 O(d) 输出，并且是比我所知道的任何其他方法都要快得多.我已经发布了这个解决方案作为答案，带有 C 源代码.它是另一位贡献者 Will Ness 在 Haskell 中介绍的漂亮算法的高度优化、简化版本.我选择 Will 的答案作为接受的答案，因为它提供了一个非常优雅的解决方案，符合最初声明的所有要求.
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.
从列表[1]开始，对于每个唯一的质因数p，我们迭代地将列表乘以pk 次(其中 k 是 p 的重数)以获得 k 个新列表，并将它们与传入列表合并在一起.
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.
在 Haskell 中，
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, y, z,...]
$ xs -- where { y=f x; z=f y; ... }
{- 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 以线性方式工作.
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 是一个标准函数，它将列表中的相邻相等组合在一起，而 factorize 是一种众所周知的试除算法，它以非递减顺序生成一个数的质因数:
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 _ = []
(.) 是一个函数组合运算符，将其右侧参数函数的输出作为输入链接到其左侧.它(和 $)可以朗读为of".
(.) 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屋！
