for k in range(2, N):
fact = # prime factors of k
for i in range(2, N):
if i has no factors in common with k:
count += N // i # We need j%k == 0; this is a simple division.
else:
divisors = # remove common i-factors from k-factors (reduce)
new_i = # product of remaining factors
count += N // new_i # j must be a multiple of "reduced" k
例如,对于k=6,我们这样迭代:
i = 1: relatively prime to k; add (10 // 6) j-values: j=6 is the only solution
i = 2: Common factor of 2; treat as k = 6/2; add (10 // 3) j-values
i = 3: Common factor of 3; treat as k = 6/3; add (10 // 2) j-values
i = 4: Common factor of 2; treat as k = 6/2; add (10 // 3) j-values
i = 5: relatively prime to k; add (10 // 6) j-values: j=6 is the only solution
有几件事你可以做来改善这一点。 该算法统计有多少(
i, j
)积可被k
整除,所有数字都在[1, N]
范围内。您可以通过明智地选择循环限制来减少开销:为了
k
除以i*j
,i
和j
必须包含k
的每个素数因子。您可以直接计算这些,而不是遍历所有的可能性。从外循环中的k
开始,确定它的素数因子,然后生成覆盖这些因子的所有i*j
组合从一个循环开始生成整个范围的素因子分解[2,N]。用埃拉托斯特尼的筛子来接近它,但不是立即取消一个合成数的资格,而是保留一份它的因素列表。例如,如果N=10,您将使用一个方便的因子分解列表来完成此循环:
现在您有了所需的每个
i j k
值的因式分解例如,对于
k=6
,我们这样迭代:你知道这是怎么回事吗
您可以进行一些额外的检查,以通过线性和次线性因素来减少开销,但是我们仍然有一个控制O(n^2)循环,如上所述
相关问题 更多 >
编程相关推荐