Python程式：查詢x之間乘積為x且互質的數對數量

假設有一個函式 f(x)，它計算滿足以下條件的 (p, q) 數對的數量：

• 1 < p <= q <= x
• p 和 q 互質
• p * q = x 如果我們有 n。

我們需要找到所有從 1 到 n 的 i 的 f(x[i]) 之和。

例如，如果輸入是 12，則輸出為 3，因為 x 的取值範圍是從 1 到 12。

• 當 x = 6 時，有效的數對是 (2, 3)，所以 f(6) = 1
• 當 x = 10 時，有效的數對是 (2, 5)，所以 f(10) = 1
• 當 x = 12 時，有效的數對是 (3, 4)，所以 f(12) = 1

所以共有 3 個數對。

為了解決這個問題，我們將遵循以下步驟：

• count := 0
• sqr := n 的平方根的整數部分 + 1
• 對於 base 從 2 到 sqr - 1，執行：
  • 對於 i 從 1 到 base 和 (n / base - base + 1) 地板函式的最小值，執行：
    • 如果 base 和 i 的最大公約數不等於 1，則
      • 跳過本次迭代
    • count := count + (n - i * base) / (base * base) 的地板函式
• 返回 count

示例

讓我們看下面的實現來更好地理解：

from math import sqrt, gcd

def solve(n):
   count = 0
   sqr = int(sqrt(n)) + 1
   for base in range(2, sqr):
      for i in range(1, min(base, n // base - base + 1)):
         if gcd(base, i) != 1:
            continue
         count += (n - i * base) // (base * base)

   return count

n = 12
print(solve(n))

輸入

12

輸出

3

Arnab Chakraborty

更新於：2021年10月23日

瀏覽量：136

啟動您的職業生涯

透過完成課程獲得認證

開始學習