Số nguyên tố đóng vai trò trung tâm trong nhiều ứng dụng như mật mã học. Vì vậy, cần kiểm tra số nguyên tố bằng chương trình Python trong các ứng dụng khác nhau. Số nguyên tố là số không có ước số nào ngoài 1 và chính nó. Dưới đây là các chương trình để kiểm tra một số cho trước có phải số nguyên tố hay không.
Cách tiếp cận
Chúng ta thực hiện theo cách sau để quyết định một số có phải nguyên tố hay không:
Kiểm tra ngay từ đầu xem số có dương hay không. Chỉ số dương mới có thể là số nguyên tố.
Chia số đó cho tất cả các số trong khoảng từ 2 đến số nhỏ hơn số cho trước 1 đơn vị.
Nếu dư bằng 0 cho bất kỳ số nào trong khoảng này, thì nó không phải số nguyên tố.
Ví dụ
x = 23
if x > 1:
for n in range(2, x):
if (x % n) == 0:
print(x, "không phải số nguyên tố")
print(n, "nhân", x // n, "là", x)
break
else:
print(x, "là số nguyên tố")
else:
print(x, "không phải số nguyên tố")
Kết quả
Chạy mã trên cho kết quả sau:
23 là số nguyên tố
Kiểm tra dạng 6k+1
Tất cả các số nguyên tố lớn hơn 6 có thể biểu diễn dưới dạng 6k+1. Ở đây k bắt đầu từ 1 và tăng dần. Trong ví dụ dưới đây, chúng ta sẽ kiểm tra xem số có thể biểu diễn dưới dạng 6k+1 bằng cách chia cho 6 và kiểm tra dư là 1. Theo đó, quyết định số có phải nguyên tố hay không. Cũng cần kiểm tra giá trị k bằng căn bậc hai của số cho trước.
Ví dụ
def kiem_tra_nguyen_to(n):
# Kiểm tra trường hợp 2 và 3
if n <= 1:
return False
if n <= 3:
return True
# Bỏ qua kiểm tra năm số giữa trong vòng lặp
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
# Kiểm tra đầu vào
if kiem_tra_nguyen_to(31):
print("true")
else:
print("false")
if kiem_tra_nguyen_to(25):
print("true")
else:
print("false")
Kết quả
Chạy mã trên cho kết quả sau:
true false