มีวิธีตรวจสอบความเป็นจำนวนเฉพาะ หรือเปล่าค่ะ ทำได้อย่างไรค่ะ ช่วยแนะนำหน่อยค่ะ
มีวิธีตรวจสอบความเป็นจำนวนเฉพาะ หรือเปล่าค่ะ ทำได้อย่างไรค่ะ ช่วยแนะนำหน่อยค่ะ?
อาจมีอยู่หลายวิธีนะครับ แต่ จะแนะนำสักวิธี
เราสามารถตรวจได้ดังนี้
สมมติเขาถามว่า 611 เป็นจำนวนเฉพาะรึเปล่า ทุกคนก็คงจะเริ่มด้วยการประมาณค่ารากที่สองของ 611 ซึ่งได้ประมาณเกือบ ๆ 24จากนั้นก็เริ่มเอาจำนวนเฉพาะไปหาร 611 ดู โดยเริ่มจาก 2 3 5 7 ไปเรื่อย ๆ แต่พอเราลองไปจนถึง 24 แล้วยังไม่มีจำนวนเฉพาะสักตัวหาร 611ลงตัว เราก็หยุดและสรุปว่า 611 เป็นจำนวนเฉพาะ โดยไม่ต้องลองเอาจำนวนเฉพาะอื่นๆ ไปหาร 611 อีกต่อไป มีวิธีคิดดังนี้คือ ให้ n เป็นจำนวนนับใด ๆ (n เป็นจำนวนเฉพาะหรือไม่ก็เป็นจำนวนประกอบเพียงอย่างใดอย่างหนึ่ง)
- สมมติว่า n เป็นจำนวนประกอบ
- จำนวนประกอบคือจำนวนที่มีจำนวนอื่นนอกจาก 1 และตัวมันเองที่หารมันลงตัว
- ดังนั้นมีจำนวนนับ a โดย a หาร n ลงตัว และ 1 < a < n
- นั่นคือจะมีจำนวนนับ b ที่ 1 < b < n และ n = a * b
- โดยไม่เสียนัยสำคัญกำหนดให้ a <= b (ถ้า a > b ก็ให้สลับค่า a กับ b)
- สังเกตว่า a = รากที่สองของ (a^2) <= รากที่สองของ (a*b) = รากที่สองของ n
ขอขอบคุณข้อมูลจาก
วิกิพีเดีย, ศูนย์วิทยาศาสตร์เพื่อการศึกษา