时间戳

首页 > 解决方案 > 这个代码块的优化版本是什么

python - 这个代码块的优化版本是什么

问题描述

cnt = 0
N = int(raw_input())
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            if (i*j)%k == 0:
                cnt+=1

给定 python 代码，是否可以进一步优化以使 cnt 值正确。我尝试过的一种方法是计算第 k 个循环中的因子，这将使复杂度从 o(n^3) 变为 o(n^2root(n))

标签： python

解决方案

您可以做几件事来改善这一点。该算法计算有多少 ( i, j) 产品可以被整除k，所有数字都在该范围内[1, N]。您可以通过明智地选择循环限制来减少开销：

for i in range(1, N+1):
    for j in range(i, N+1):
        for k in range(i*j, N+1):
            if (i*j) % k == 0:
                cnt += 1

为k除i*j，i且j必须包含k所需数量中的每个素因子。您可以直接计算这些，而不是遍历所有可能性。从外部循环开始k，确定其主要因素，然后生成i*j将涵盖这些因素的所有组合。

从一个循环开始，为整个范围 [2,N] 生成素数分解。接近它过着埃拉托色尼的筛子，但不是立即取消合数的资格，而是保留其因子的列表。例如，如果 N=10，您将使用一个方便的分解列表完成此循环：

 2   2
 3   3
 4   2 2
 5   5
 6   2 3
 7   7
 8   2 2 2
 9   3 3
10   2 5

现在您可以分解所需的每个i j k值。

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

你明白它是如何工作的吗？

您可以进行一些额外的检查，以通过线性和次线性因素减少开销，但我们仍然有一个控制O(n^2)循环，如上所述。

推荐阅读