Question

[PYTHON]

Hai số tự nhiên m,n được gọi là nguyên tố cùng nhau nếu UCLN(m,n)=1.

Viết chương trình thực hiện công việc sau: Nhập từ bàn phím số tự nhiên n và đếm số các số nguyên tố cùng nhau với n tính trong khoảng từ 1 đến n.

Answer 1

def is_coprime(a, b):
    """Hàm ktra a và b có phải là nguyên tố cùng nhau"""
    while b:
        a, b = b, a % b
    return a == 1

n = int(input("Nhập stn n: "))
count = 0

for i in range(1, n+1):
    if is_coprime(i, n):
        count += 1

print(f"Số lượng số nguyên tố cùng nhau với n là {count}.")