บทสรุปของโพสต์โดย durumis AI
ใน Java การตรวจสอบจำนวนเฉพาะแบบเดิมโดยการหารด้วยจำนวนตั้งแต่ 2 ถึง n-1 นั้นมีประสิทธิภาพไม่สูง บทความนี้เสนอวิธีการปรับปรุงโดยการตรวจสอบแค่ถึง sqrt(n) และการใช้รูปแบบ 6k±1 การใช้ Stream ช่วยให้สามารถประยุกต์ใช้ lazy evaluation เพื่อสร้าง Stream ที่คำนวณหาจำนวนเฉพาะเฉพาะเมื่อจำเป็นเท่านั้น การปรับปรุงและวิธีการใช้ Stream ที่เสนอในบทความนี้ช่วยให้สามารถพัฒนาอัลกอริทึมการตรวจสอบจำนวนเฉพาะได้อย่างมีประสิทธิภาพมากขึ้น โดยทั่วไปแล้ว การตรวจสอบว่า 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 ที่หาจำนวนเฉพาะได้ดังนี้
ผลลัพธ์