我需要得到比為質數的任何數（最多 10e9）的所有除數。
考慮某個整數 n 的所有除數。選擇這些除數中的一些，然后將它們排列成一個圓圈，使任意兩個相鄰數的比為質數。找出你可以選擇的 n 的最大除數，并找到合適的排列。
例如：
input: 10
output: 1 2 10 5
2 = 1 * 2 ; 10 = 2 * 5 ; 5 = 1 * 5
另外一個輸出陣列必須是一個回圈（circle）。因此第一個和最后一個數字的比率必須是質數。
我試圖找到給定數字的所有除數并生成它們的所有可能排列并檢查每個排列：
from itertools import permutations
n = int(input())
d = list(filter(lambda x: not n % x, range(1, n 1)))
for i in range(1, len(d)):
print(list(permutations(d, i)))
# check the permutation
但這是一個糟糕的解決方案，因為它的作業時間很長。誰能建議一種演算法來更有效地解決我的問題？
uj5u.com熱心網友回復：
您可以通過將其轉換為在圖中查找最長路徑來解決此問題（盡管這是 NP-Hard 并且可能不會更快）。
該圖將由與因子對應的節點和以因子之間的質數比連接節點的邊組成。
您首先需要一個函式來給出一個數的所有質因數（包括重復質數）：
def primeFactors(N):
d = 2
while d*d<=N:
while N%d==0:
yield d
N //= d
d = 1
if N>1: yield N
然后，您可以將所有這些質因子組合到一個因子字典中，其中值是一組其他因子，這些因子與每個因子 {factor:{factor with prime ratio}..} 處于質數比。這將是您的圖表。
def factorGraph(N):
primes = list(primeFactors(N))
factors = {1:set(primes)}
for p in primes:
factors.update({p*f:set() for f in factors})
for p in set(primes):
for f in factors:
if f%p==0:
factors[f].add(f//p)
factors[f//p].add(f)
return factors
然后使用遞回函式找到從起始因子到給定目標節點（從目標節點本身的相關節點開始）的最長圓形路徑。該函式不得多次使用相同的因子，因此它會向下推一組訪問過的節點（已看到）以將它們從更深層次的搜索中排除。
def longestCircle(graph,target,fromFactor=0,seen=set()):
longest = []
remaining = graph[fromFactor or target] - seen # eligible next factors
for factor in remaining: # Try each factor
path = [factor] # form a path
if factor != target: # must reach target
path = longestCircle(graph,target,factor,seen|{factor})
if path[-1]==target and len(path)>=len(longest):
longest = path # keep longest path
if len(path)==len(graph): return path # all factors used
return longest
最后，最長的回圈因子路徑將是具有最多元素的路徑。
def factorCircle(N):
graph = factorGraph(N)
return max((longestCircle(graph,first) for first in graph),key=len)
請注意，這是從每個可能的起始因素進行檢查，以防較長的路徑跳過其中一個因素，但很可能 1 總是在回圈中，因此可能會矯枉過正回傳longestCircle(graph,1) 可能就足夠了，但我不這樣做沒有時間證明它是（或不是）。
輸出：
print(factorCircle(10)) # [5, 10, 2, 1] # 4 of 4 factors
print(factorCircle(30)) # [5, 15, 30, 10, 2, 6, 3, 1] # 8 of 8
print(factorCircle(512)) # [2, 1] # 2 of 10
print(factorCircle(660))
# [5, 15, 30, 6, 66, 22, 110, 220, 44, 4, 2, 10, 20, 60, 12,
132, 660, 330, 165, 55, 11, 33, 3, 1] # 24 of 24
uj5u.com熱心網友回復：
我正在添加一個新答案，因為我想到了一個非常不同的程序來獲取除數串列。
我沒有關注因子，而是創建了一系列質數比（乘法和除法）。鑒于我們需要回圈回到初始值，每個乘法比率最終都必須跟隨相同比率的相應除法。所以我們只需要找到質數乘法和除法的正確順序（使用數字的質因數）。
例如，6 的質因數是 2 和 3，因數是 1、2、3 和 6。因數之間的比率將是 2 或 3。從 1 開始，我們可以有一個比率序列：x2、x3 , /2, /3 這將產生因子序列：1, 2, 6, 3, 1。（最后一個是環回到 1）。這將每個 xPrime 與相應的 /Prime 平衡，確保回圈完成。
如果我們加上一個質因數 (5) 并轉到 30，質因數是 2、3 和 5，現在的因數是 1、2、3、6、5、10、15 和 30。
當有兩個以上的素數因子時，比率序列可以遞回地“堆疊”在每個素數的頂部（用作基線）。這意味著一系列因子（例如 3,5 --> x3, x5, /3, /5）可以獨立并回傳到原始值 (1) 但它也可以從不同的基線開始（例如2) 并且會回到它而不產生它從 1 基線具有的任何因素：
from 1: (x3, x5, /3, /5) --> 3, 15, 5, 1
from 2: (x3, x5, /3, /5) --> 6, 30, 10, 2
- 2 的基本序列是
x2, /2 - 在 x2 基線上堆疊 3 和 5，我們將有：
x2, <stack 3 and 5> , /2
- 3 和 5 的順序是
x3, x5, /3, /5 - 給予：
x2, x3, x5, /3, /5 , /2 - 但是堆疊序列的最后一個除法 (/5) 會產生一個重復因子，因為該序列會回圈回到基線。
- 因此，我們將最后一個磁區 (/5) 與下一個磁區 (/2) 交換：
- 給予：
x2, x3, x5, /3, /2, /5 - 導致的因素：
2, 6, 30, 10, 5, 1
當有 4 個或更多質因子時，這也按順序適用，方法是回圈回到每個質數并將其余因子堆疊在其上（作為新的唯一基線）。
對于重復的質因數，只要 xP 和 /P 不連續，xP 和 /P 就可以重復。因此，對于 20 (2,2,5) 初始序列 (x2, x5, /2, /5) 可以擴展為 (x2, x2, x5, /2, /2, /5) 給出因子 (2, 4、20、10、5、1)。然而，對于 8 (2,2,2)，序列是 (x2, /2) 所以我們不能重復這些比率。
這類似于通過從每個值（在這種情況下為主要因素）開始并從剩余值中添加組合模式來遞回構建組合的方式
這仍然需要一個素數分解函式：
def primeFactors(N):
d = 2
while d*d<=N:
while N%d==0:
yield d
N //= d
d = 1
if N>1: yield N
比率序列函式是遞回的，使用正數表示乘法，使用負數表示除法（例如 x2, x3, /2, /x --> [2, 3, -2, -3]）
def getRatios(factors):
rFactors = list(factors) # repeatable prime factors
uFactors = set(rFactors) # unique prime factors
ratios = [] # resulting sequence of ratios
while uFactors: # new baseline for each prime
if not ratios: # first multiplication
f = min(uFactors)
ratios = [f,-f] # positive = multiply, negative = divide
else: # extend recursively
fr = getRatios(rFactors) # pattern over baseline
if not fr: break
fr.insert(-1,ratios.pop(-1)) # swap last divisions
ratios.extend(fr) # extend ratio sequence
f = abs(ratios[-1]) # last used prime factor
rFactors = [r for r in rFactors if r!=f] # remove last used prime
uFactors.discard(f) #
for i,f in enumerate(reversed(ratios),1-len(ratios)): # repeat primes
i = -i
if f<0 and ratios[i-1:i 1 or None] == [-f,f]: continue
if f>0 and ratios[i:i 2 or None] == [f,-f]: continue
count = factors.count(abs(f))
if count > 1: ratios[i:i] = [f]*(count-1) # expand repeated prime
return ratios
最終結果是通過從基線 1 開始按順序應用比率獲得的（不包括最后一個磁區，因為我們只需要看到 1 一次：
def factorCircle2(N):
ratios = getRatios([*primeFactors(N)]) # get ratio sequence
result = [1] # startfactors at 1
for r in ratios[:-1]: # apply ratios to get factors
result.append(result[-1]*r if r>0 else result[-1]//-r)
return result
輸出：
print(factorCircle2(10)) # [1, 2, 10, 5] # 4 of 4 factors
print(factorCircle2(30)) # [1, 2, 6, 30, 10, 5, 15, 3] # 8 of 8
print(factorCircle2(512)) # [1, 2] # 2 of 10
print(factorCircle2(660))
# [1, 2, 4, 12, 60, 660, 132, 44, 220, 20, 10, 30, 330, 110, 22,
66, 6, 3, 15, 165, 33, 11, 55, 5] # 24 of 24
print(factorCircle2(60060))
# [1, 2, 4, 12, 60, 420, 4620, 60060, 5460, 780, 8580, 660, 132, 924,
12012, 1716, 156, 1092, 84, 28, 140, 1540, 20020, 1820, 364, 4004,
308, 44, 220, 2860, 572, 52, 260, 20, 10, 30, 210, 2310, 30030,
2730, 390, 4290, 330, 110, 770, 10010, 1430, 130, 910, 70, 14, 42,
462, 6006, 546, 182, 2002, 154, 22, 66, 858, 286, 26, 78, 6, 3, 15,
105, 1155, 15015, 1365, 195, 2145, 165, 33, 231, 3003, 429, 39, 273,
21, 7, 35, 385, 5005, 455, 91, 1001, 77, 11, 55, 715, 143, 13, 65,
5] # 96 of 96 factors
經過一些測驗，我相信這涵蓋了所有情況，并且性能比基于圖形的解決方案要好得多。
注意：我發現調整后的代碼存在另一個問題，當存在重復素數時，有時會阻止它達到最大回圈長度
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/380285.html
上一篇：Bloxorza-Star搜索
下一篇：團隊生成器的演算法