Để 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 phương pháp sàng Eratosthenes. Phương pháp này cho phép tìm tất cả các số nguyên tố trong một khoảng cho trước.
Dưới đây là một ví dụ về cách thực hiện phương pháp sàng Eratosthenes để liệt kê tất cả các số nguyên tố cùng nhau với một số nguyên dương n cho trước:
def sieve(n):
# Khởi tạo một danh sách chứa các số từ 2 đến n
numbers = [True] * (n + 1)
primes = []
# Loại bỏ các số không phải số nguyên tố bằng phương pháp sàng Eratosthenes
p = 2
while p * p <= n:
if numbers[p]:
for i in range(p * p, n + 1, p):
numbers[i] = False
p += 1
# Lưu trữ các số nguyên tố cùng nhau với n vào danh sách primes
for p in range(2, n + 1):
if numbers[p] and are_coprime(p, n): # Kiểm tra số nguyên tố có cùng nhau với n
primes.append(p)
return primes
def are_coprime(a, b):
# Hàm kiểm tra xem hai số a và b có cùng nhau hay không
while b != 0:
a, b = b, a % b
return a == 1
# Sử dụng hàm sieve() để liệt kê tất cả các số nguyên tố cùng nhau với một số nguyên dương n cho trước
n = 20
result = sieve(n)
print(result)
Độ phức tạp của thuật toán sàng Eratosthenes là O(n log(log n)), trong đó n là số nguyên dương cho trước.