Thuật toán kiểm tra Python Prime
Kiểm tra xem một số có phải là số nguyên tố hay không bằng Python Chạy thuật toán tương tác của chúng tôi để xem phép lặp toán học và đánh giá nghiệm hiệu quả.
Tổng quan
Số nguyên tố là số nguyên dương lớn hơn 1, không có ước số dương nào khác ngoài 1 và chính nó.
Cách kém hiệu quả nhất để kiểm tra số nguyên tố là lặp lại chính số đó. Một cách tối ưu hóa mạnh mẽ là chỉ kiểm tra khả năng chia hết cho đến căn bậc hai của số.
Đầu ra mã & thực thi
Thuật toán kiểm tra số nguyên tố hiệu quả thể hiện tối ưu hóa O(sqrt(n)).
import math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
max_divisor = math.isqrt(n)
for i in range(3, max_divisor + 1, 2):
if n % i == 0:
return False
return True
test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
status = "Prime" if is_prime(num) else "Not Prime"
print(f"{num:2d} -> {status}") 2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> PrimeTriển khai từng bước
- Thuật toán mật mã và băm
- Toán giáo dục và lý thuyết sàng
- Xác thực phụ trợ cho các khóa bảo mật
Câu hỏi thường gặp
Tại sao chỉ kiểm tra đến căn bậc hai?
Nếu $n = a \times b$, thì ít nhất một trong các thừa số ($a$ hoặc $b$) phải nhỏ hơn hoặc bằng căn bậc hai của $n$. Vì vậy, việc kiểm tra cao hơn là dư thừa.
Chủ đề liên quan
Chạy và hiểu dãy Fibonacci trong Python. Ví dụ về mã tương tác này cho thấy các phương pháp lặp và đệ quy để tạo số Fibonacci.
Thuật toán sắp xếp PythonKhám phá các thuật toán sắp xếp python. Trực quan hóa sắp xếp bong bóng và sắp xếp hợp nhất nguyên bản trong ngữ cảnh IDE của trình duyệt.