Đếm cặp (p,q) nguyên tố cùng nhau, p*q=x, 1

Cho hàm f(x) đếm số cặp (p,q) thỏa: 1 < p ≤ q ≤ x, gcd(p,q)=1, p*q=x. Tính tổng f(x) cho x từ 1 đến n.

Ví dụ: n=12 → kết quả 3. Các cặp: (2,3) cho x=6, (2,5) cho x=10, (3,4) cho x=12.

Giải thuật

• Duyệt base từ 2 đến sqrt(n).
• Với mỗi base, duyệt i từ 1 đến min(base, n//base - base + 1).
• Nếu gcd(base, i) == 1: cộng thêm (n - i*base) // (base*base).

Ví dụ mã 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))  # Output: 3

Đầu vào

12

Đầu ra

3