[Java] ใช้ Stream ค้นหาจำนวนเฉพาะแบบ Lazy

โดยทั่วไปแล้ว การตรวจสอบว่า n เป็นจำนวนเฉพาะหรือไม่นั้น จะทำการหาร n ด้วยจำนวนเต็มตั้งแต่ 2 ไปจนถึง n - 1 และตรวจสอบว่ามีจำนวนใดหาร n ลงตัวหรือไม่

ลองมาปรับปรุงวิธีการนี้ให้มีประสิทธิภาพมากขึ้นโดยการเพิ่มขั้นตอนการปรับแต่งบางอย่าง และลองใช้ Stream เพื่อใช้ประโยชน์จากการประเมินแบบล่าช้า (lazy evaluation)

วิธีการแบบพื้นฐาน (Naive)

ต่อไปนี้เป็นวิธีการแบบพื้นฐานในการตรวจสอบว่า n เป็นจำนวนเฉพาะหรือไม่

การปรับปรุง

• เมื่อ n = a x b เราสามารถสมมติได้ว่า a > b โดยไม่สูญเสียลักษณะทั่วไป
  นั่นหมายความว่า เราสามารถตรวจสอบ i ได้เพียงแค่ถึง sqrt(n) เท่านั้น เนื่องจากการคำนวณ sqrt() นั้นค่อนข้างสิ้นเปลือง เราจึงสามารถแทนที่ด้วยเงื่อนไข i * i <= n ได้
• จำนวนเฉพาะที่มากกว่า 5 จะอยู่ในรูปแบบ 6k ± 1 ดังนั้น เราสามารถเพิ่ม i ทีละ 6 และตรวจสอบได้ ซึ่งจะช่วยลดจำนวนครั้งในการตรวจสอบลง

วิธีการที่ปรับปรุงแล้ว

การใช้ Stream เพื่อประยุกต์ใช้การประเมินแบบล่าช้า

Stream ใน Java นั้นแตกต่างจาก List ตรงที่การดำเนินการจะไม่ถูกดำเนินการทันทีที่นิยาม

Stream จะรอจนกว่าจะมีการร้องขอองค์ประกอบใดองค์ประกอบหนึ่ง แล้วจึงดำเนินการเฉพาะการคำนวณที่จำเป็นสำหรับองค์ประกอบนั้นเท่านั้น

เราสามารถใช้ประโยชน์จากคุณสมบัตินี้ในการสร้าง Stream ที่หาจำนวนเฉพาะได้ดังนี้

ผลลัพธ์

โค้ดทั้งหมด

ผลลัพธ์การทำงาน