โจทย์ข้อนี้ต้องการให้เราหาจำนวนเฉพาะที่ใหญ่ที่สุด และเป็นตัวประกอบของ N โดย
ที่ 10 <=N<= 10^12
แนวคิด เมื่อผมเห็นข้อนี้ สิ่งที่ผมคิดไว้ตอนแรกคือการรันลูปไล่ตั้งแต่ 2 จนถึง N/2 เพื่อหาตัวที่หารลงตัว เมื่อได้ตัวที่หารลงตัว ก็นำไปเช็คต่อว่าเป็นจำนวนเฉพาะไหม แต่ถ้าลองคิดดีๆแล้วการที่ N มีค่าเยอะๆ แล้ว factor ของ N มีจำนวนเฉพาะที่ค่าเยอะ ก็จะเสียเวลาในการเช็คอย่างมาก ผมก็เลยนึกถึงการหา factor สมัยตอนมัธยมต้น เพราะเนื่องจากจำนวนเต็มบวกสามารถเขียนอยู่ในรูปผลคูณ
ของจำนวนเฉพาะได้
จากรูปด้านบน คือการหา factor ของ 160 เราเริ่มจากเอา 2 ซึ่งเป็นจำนวนเฉพาะที่เล็กที่สุด ที่สามารถหาร 160 ได้ไปหารจนกว่าจะหารไม่ได้ หากเราทำการหารด้วยจำนวนเฉพาะจนกว่าจะหารไม่ได้ไปเรื่อยๆแล้วๆ สุดท้ายแล้วเราก็จะได้จำนวนเฉพาะที่ใหญ่ที่สุดออกมา (จำนวนเฉพาะที่เล็กที่สุด ของจำนวนประกอบ N ใดๆ จะมีค่าน้อยกว่าหรือเท่ากับ sqrt(N))
เราสามารถนำแนวคิดนี้ไปเขียนเป็นโค้ดในภาษาซีได้แบบนี้
ไม่มีความคิดเห็น:
แสดงความคิดเห็น