乗算がxであり、Pythonで互いに素であるx間のペアの数を見つけるプログラム

（p、q）ペアの数を数える関数f（x）があり、次のようになっているとします。

• 1

• pとqは互いに素です
• p * q =xしたがって、nがある場合。

1からnの範囲のすべてのiの合計f（x [i]）を見つける必要があります。

したがって、入力が12の場合、x値は1から12の範囲であるため、出力は3になります。

• 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の整数部分
• 2からsqr-1の範囲の塩基については、
  • 範囲1からベースとフロアの最小値（n/ベース-ベース+1）のiの場合、
    • ベースのgcdとi）が1と同じでない場合、
      • 次の反復に進む
    • count：=count + floor of（n --i * base）/（base * base）
• 返品数

例

理解を深めるために、次の実装を見てみましょう-

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