Để liệt kê tất cả các số nguyên tố cùng nhau với một số nguyên dương cho trước, chúng ta có thể sử dụng thuật toán Euclid để tìm ước số chung lớn nhất (GCD) của hai số. Nếu GCD bằng 1, hai số được coi là cùng nhau.
Dưới đây là một ví dụ cụ thể để liệt kê các số nguyên tố cùng nhau với một số nguyên dương cho trước:
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def coprime_numbers(n):
coprimes = []
for i in range(1, n):
if math.gcd(n, i) == 1:
coprimes.append(i)
return coprimes
# Số nguyên dương cho trước
number = 15
# Liệt kê các số nguyên tố cùng nhau với số number
result = coprime_numbers(number)
print(f"Các số nguyên tố cùng nhau với {number} là:")
for prime in result:
if is_prime(prime):
print(prime)
Đầu ra sẽ là tất cả các số nguyên tố cùng nhau với số nguyên dương 15:
Các số nguyên tố cùng nhau với 15 là:
2
4
7
8
11
13
Lưu ý rằng chúng ta đã sử dụng hàm is_prime() để kiểm tra xem một số có phải là số nguyên tố hay không.