我需要找到满足以下条件的数N的对(i,j)和对数:1 <= i <= j <= N且i * i * i = j * j.
以N = 50为例，配对数为3，即(1,1),(4,8),(9,27)。
我尝试了下面的函数代码，但是对于像N = 10000或更多这样的大数字需要太多时间:
def compute_pairs(N):
pair = []
for i in range (1, N):
for j in range (i, N):
print( 'j =', j)
if i*i*i == j*j:
new_pair = (i,j)
pair.append(new_pair)
print(pair)
return len(pair)
设k为满足i*i*i == j*j的整数i的平方根，其中j也是整数。因为k是整数的平方根，所以k*k也是整数。由式可知，j等于k*k*k，因此它也是一个整数。
由于k*k*k是整数，k*k是整数，因此将两者相除，k是有理数。但是k是整数的平方根，所以它要么是整数，要么是无理数。因为它是有理数，所以它必须是整数。
因为k是一个整数，所以对于整数k，所有的解都是简单的(k*k, k*k*k)。因为我们将迭代k>=1，我们知道k*k <= k*k*k，即i <= j，所以我们不必担心。我们只需要在k*k*k到达N时停止迭代。
from itertools import count # unbounded range; we will `break` when appropriate
def compute_pairs(N):
result = []
for k in count(1):
i, j = k*k, k*k*k
if j >= N:
break
result.append((i, j))
return result
即使N的值是100000，它也几乎可以立即运行，不需要c级优化。
思考这个问题。你需要i的立方等于j的平方吗?
我们知道像(0, 0)、(1, 1)、(4, 8)和(9, 27)这样的对满足这个条件。
0、1、4和9有什么共同之处?
它们是0,1,2和3的平方。
0,1,8和27有什么共同之处?
它们是相同的数的立方。
一旦你意识到这个模式，答案可以在极短的时间内计算出来。