โปรแกรมหาจำนวนคู่ระหว่าง x ซึ่งมีการคูณเป็น x และเป็น coprime ใน Python

สมมติว่ามีฟังก์ชัน f(x) ที่นับจำนวนคู่ (p, q) เช่นนั้น

• 1

• p และ q เป็น coprime
• p * q =x ถ้าเรามี n.

เราต้องหาผลรวม f(x[i]) สำหรับ i ทั้งหมดในช่วง 1 ถึง n

ดังนั้น หากอินพุตเท่ากับ 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 คู่

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• นับ :=0
• sqr :=ส่วนจำนวนเต็มของ (รากที่สองของ n) + 1
• สำหรับฐานในช่วง 2 ถึง sqr - 1 ทำ
  • สำหรับ i ในช่วง 1 ถึงขั้นต่ำของฐานและพื้นของ (n / ฐาน - ฐาน + 1) ทำ
    • ถ้า gcd ของเบสและ i) ไม่เหมือนกับ 1 แล้ว
      • ติดตามตอนต่อไป
    • นับ :=นับ + ชั้นของ (n - i * ฐาน)/(ฐาน * ฐาน)
• จำนวนคืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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