Question

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 yêu cầu sau:

- Nhập vào số tự  nhiên n từ bàn phím.

- Viết hàm tìm UCNL() của 2 số bất kỳ. Sử dụng hàm này để kiểm tra và in ra màn hình số lượng số nguyên tố cùng nhau với n trong phạm vi từ 1 đến n.

Answer 1

def UCLN(a, b):
    while(b != 0):
        a, b = b, a % b
    return a

def so_nguyen_to_cung_nhau(n):
    count = 0
    for i in range(1, n+1):
        if UCLN(n, i) == 1:
            count += 1
    return count

n = int(input("Nhập vào số tự nhiên n: "))
print("Số lượng số nguyên tố cùng nhau với", n, "trong phạm vi từ 1 đến", n, "là:", so_nguyen_to_cung_nhau(n))