Số Carmichael là các số tự nhiên n không phải số nguyên tố, nhưng mọi a thỏa mãn điều kiện (a, n) = 1, ta đều có a^(n-1) ≡ 1 (mod n).
Để tìm tất cả các số Carmichael nhỏ hơn hoặc bằng một số nguyên dương n cho trước, chúng ta có thể kiểm tra từng số trong khoảng từ 1 đến n và xác định xem số đó có phải là số Carmichael hay không.
Dưới đây là một đoạn mã Python để tìm tất cả các số Carmichael nhỏ hơn hoặc bằng một số nguyên dương cho trước:
def gcd(a, b):
while b:
a, b = b, a % b
return a
def power_mod(base, exponent, modulus):
result = 1
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % modulus
base = (base * base) % modulus
exponent = exponent // 2
return result
def is_carmichael_number(n):
if n < 2 or n % 2 == 0:
return False
for a in range(2, n):
if gcd(a, n) == 1 and power_mod(a, n-1, n) != 1:
return False
return True
def find_carmichael_numbers(limit):
carmichael_numbers = []
for n in range(1, limit+1):
if is_carmichael_number(n):
carmichael_numbers.append(n)
return carmichael_numbers
limit = int(input("Nhập một số nguyên dương: "))
carmichael_numbers = find_carmichael_numbers(limit)
print("Các số Carmichael nhỏ hơn hoặc bằng", limit, "là:")
print(carmichael_numbers)
Bạn có thể nhập một số nguyên dương để tìm tất cả các số Carmichael nhỏ hơn hoặc bằng nó. Đoạn mã sẽ in ra danh sách các số Carmichael tìm thấy. Lưu ý rằng việc tìm số Carmichael có thể mất thời gian với các giá trị lớn.