Chương trình tìm số cặp giữa x, có phép nhân là x và chúng là số nguyên tố trong Python

Giả sử có một hàm f (x), đếm số cặp (p, q), sao cho

1
p và q là cùng chuẩn
p * q =x Vì vậy, nếu chúng ta có n.

Chúng ta phải tìm tổng f (x [i]) cho mọi i trong phạm vi từ 1 đến n.

Vì vậy, nếu đầu vào là 12, thì đầu ra sẽ là 3, vì các giá trị x nằm trong khoảng từ 1 đến 12.

Khi x =6, cặp hợp lệ là (2, 3) nên f (6) =1
Khi x =10, cặp hợp lệ là (2, 5) nên f (10) =1
Khi x =12, cặp hợp lệ là (3, 4) nên f (12) =1

vì vậy có tổng cộng 3 cặp.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

số lượng:=0
sqr:=phần nguyên của (căn bậc hai của n) + 1
đối với cơ sở trong phạm vi 2 đến sqr - 1, thực hiện
- đối với tôi trong phạm vi từ 1 đến tối thiểu của cơ sở và tầng của (n / cơ sở - cơ sở + 1), thực hiện
  - nếu gcd của cơ sở và i) không giống với 1, thì
    - chuyển sang lần lặp tiếp theo
  - count:=count + tầng của (n - i * base) / (base * base)
số lượng trả lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Chương trình tìm số cặp giữa x, có phép nhân là x và chúng là số nguyên tố trong Python

Ví dụ

Đầu vào

Đầu ra