Trong hướng dẫn này, ta sẽ khám phá các phương pháp khác nhau để tìm xem một số cho trước có phải số nguyên tố hay không. Bắt đầu ngay.
Phương pháp 1
Đây là phương pháp chung để tìm số nguyên tố.
- Nếu số ≤ 1, trả về False.
- Nếu số chia hết cho bất kỳ số nào, hàm trả về False.
- Sau vòng lặp, trả về True.
Ví dụ
# kiểm tra số nguyên tố def is_prime(n): if n <= 1: return False else: for i in range(2, n): # kiểm tra ước if n % i == 0: return False return True print(f"2 là nguyên tố: {is_prime(2)}") print(f"4 là nguyên tố: {is_prime(4)}") print(f"7 là nguyên tố: {is_prime(7)}")Kết quả
Nếu chạy mã trên, ta được kết quả sau.
2 là nguyên tố: True 4 là nguyên tố: False 7 là nguyên tố: True
Phương pháp 2
Trong phương pháp này, ta giảm số lần lặp bằng cách cắt ở căn bậc hai của n. Xem mã.
Ví dụ
import math # kiểm tra số nguyên tố def is_prime(n): if n <= 1: return False else: # lặp đến căn bậc hai của n for i in range(2, int(math.sqrt(n)) + 1): # kiểm tra ước if n % i == 0: return False return True print(f"2 là nguyên tố: {is_prime(2)}") print(f"4 là nguyên tố: {is_prime(4)}") print(f"7 là nguyên tố: {is_prime(7)}")Kết quả
Nếu chạy mã trên, ta được kết quả sau.
2 là nguyên tố: True 4 là nguyên tố: False 7 là nguyên tố: True
Phương pháp 3
Trong phương pháp trước, ta đã kiểm tra số chẵn. Ta biết số chẵn không thể là nguyên tố trừ 2. Vì vậy, phương pháp này loại bỏ tất cả số chẵn để giảm thời gian.
Ví dụ
import math # kiểm tra số nguyên tố def is_prime(n): # kiểm tra nhỏ hơn 1 if n <= 1: return False # kiểm tra 2 elif n == 2: return True elif n > 2 and n % 2 == 0: return False else: # lặp đến căn bậc hai của n, bước 2 for i in range(3, int(math.sqrt(n)) + 1, 2): # kiểm tra ước if n % i == 0: return False return True print(f"2 là nguyên tố: {is_prime(2)}") print(f"4 là nguyên tố: {is_prime(4)}") print(f"7 là nguyên tố: {is_prime(7)}")Kết quả
Nếu chạy mã trên, ta được kết quả sau.
2 là nguyên tố: True 4 là nguyên tố: False 7 là nguyên tố: True
Kết luận
Nếu có thắc mắc, hãy để lại bình luận.