โปรแกรมนับคู่ (p,q) ที่ p*q=x และ p,q เป็นสหภาคใน Python

กำหนดฟังก์ชัน f(x) นับจำนวนคู่ (p,q) ที่ 1 < p ≤ q ≤ x, gcd(p,q)=1, และ p*q=x ต้องการหาผลรวม f(x) สำหรับ x=1 ถึง n

ตัวอย่าง: n=12 ผลลัพธ์คือ 3 เพราะคู่ที่ถูกต้องคือ (2,3) สำหรับ x=6, (2,5) สำหรับ x=10, (3,4) สำหรับ x=12

ขั้นตอนการแก้ปัญหา

1. วนลูป base จาก 2 ถึง sqrt(n)
2. สำหรับแต่ละ base วน i จาก 1 ถึง min(base, n//base - base + 1)
3. หาก gcd(base, i) == 1 ให้บวก (n - i*base) // (base*base) เข้ากับนับ

ตัวอย่างโค้ด Python

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))  # ผลลัพธ์: 3

อินพุตตัวอย่าง

12

เอาต์พุตตัวอย่าง

3