Khi xác định số nguyên tố trong Java, bài viết đề xuất phương pháp cải thiện hiệu quả của phương pháp truyền thống kiểm tra xem số đó có chia hết cho các số từ 2 đến n-1 hay không bằng cách chỉ kiểm tra đến sqrt(n) và sử dụng dạng 6k±1.
Sử dụng Stream cho phép áp dụng đánh giá lười biếng, giúp tạo ra một Stream tìm số nguyên tố chỉ thực hiện phép toán khi cần thiết.
Các cải tiến và cách sử dụng Stream được đề xuất sẽ giúp triển khai thuật toán xác định số nguyên tố hiệu quả hơn.
Thông thường, để kiểm tra xem n có phải là số nguyên tố hay không, người ta sẽ chia n cho các số từ 2 đến n - 1 và kiểm tra xem n có chia hết cho số nào trong khoảng đó hay không.
Trong phương pháp này, hãy áp dụng một vài tối ưu hóa để cải thiện hiệu quả hơn nữa và sử dụng Stream để áp dụng đánh giá lười biếng (lazy evaluation).
Phương pháp đơn giản (Naive)
Dưới đây là một phương pháp đơn giản để kiểm tra xem n có phải là số nguyên tố hay không.
Các cải tiến
Khi biểu diễn n = a x b, ta có thể giả sử a > b mà không làm mất tính tổng quát. Điều đó có nghĩa là ta chỉ cần kiểm tra i đến sqrt(n). Tuy nhiên, phép toán sqrt() khá tốn kém, vì vậy ta có thể thay thế bằng điều kiện i * i <= n.
Các số nguyên tố lớn hơn 5 đều có dạng 6k ± 1. Do đó, ta có thể tăng i lên 6 đơn vị mỗi lần và kiểm tra, giúp giảm số lần kiểm tra.
Phương pháp cải tiến
Áp dụng đánh giá lười biếng (Lazy Evaluation) với Stream
Stream trong Java khác với List ở chỗ các phép toán không được thực hiện ngay lập tức khi được định nghĩa.
Thay vào đó, chúng ở trạng thái chờ, chỉ định cách tính toán cho từng phần tử, và chỉ thực hiện phép tính khi cần thiết để lấy ra một phần tử cụ thể.
Sử dụng tính năng này, ta có thể tạo ra một Stream tìm các số nguyên tố như sau: