这个代码b的优化版本是什么

2024-03-29 01:06:43 发布

您现在位置: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))


Tags: 方法代码inforinputrawifrange
1条回答
网友
1楼 · 发布于 2024-03-29 01:06:43

有几件事你可以做来改善这一点。 该算法统计有多少(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*jij必须包含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)循环,如上所述

相关问题 更多 >