Các số nguyên tố đóng một vai trò trung tâm trong nhiều ứng dụng e it như mật mã. Vì vậy, việc kiểm tra các số nguyên tố bằng các chương trình Python trong các ứng dụng khác nhau là điều cần thiết. Số nguyên tố là một số không có bất kỳ thừa số nào ngoài một và chính nó. Dưới đây sẽ thấy các chương trình có thể tìm hiểu xem một số đã cho có phải là số nguyên tố hay không.
Phương pháp tiếp cận
Chúng tôi thực hiện phương pháp sau để quyết định xem một số có phải là số nguyên tố hay không.
-
Kiểm tra lúc đầu có dương tính hay không. Vì chỉ số dương mới có thể là số nguyên tố.
-
Chúng tôi chia số có tất cả các số trong phạm vi từ 2 đến một số nhỏ hơn số đã cho.
-
Nếu phần còn lại trở thành 0 đối với bất kỳ số nào trong phạm vi này thì nó không phải là số nguyên tố.
Ví dụ
x = 23 if x > 1: for n in range(2, x): if (x % n) == 0: print(x, "is not prime") print(n, "times", x // n, "is", x) break else: print(x, "is a prime number") else: print(x, "is not prime number")
Đầu ra
Chạy đoạn mã trên cho chúng ta kết quả sau -
23 is a prime number
Kiểm tra biểu mẫu 6i + 1
Tất cả các số nguyên tố lớn hơn 6 có thể được biểu diễn dưới dạng 6i + 1. Ở đây tôi bắt đầu từ 1 và tiếp tục là số nguyên. Trong ví dụ dưới đây, chúng tôi sẽ kiểm tra xem số có thể được trình bày ở dạng 6i + 1 hay không bằng cách chia 6 của nó và kiểm tra lời nhắc là một. Theo đó, sẽ quyết định xem số đó có phải là số nguyên tố hay không. Ngoài ra, chúng ta cần kiểm tra giá trị i bằng căn bậc hai của số đã cho.
Ví dụ
def CheckPrime(n):
# Check for cases of 2 and 3
if (n <= 1):
return False
if (n <= 3):
return True
# skip checking middle five numbers in the loop
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 = i + 6
return True
# Check for inputs
if (CheckPrime(31)):
print(" true")
else:
print(" false")
if (CheckPrime(25)):
print(" true")
else:
print(" false") Đầu ra
Chạy đoạn mã trên cho chúng ta kết quả sau -
true false