[Java] Sử dụng Stream để tìm số nguyên tố một cách lười biếng

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:

Kết quả thực thi

Toàn bộ mã nguồn

Kết quả thực thi