จำนวนเฉพาะ คือ จำนวนเต็มบวกที่มากกว่า 1 และมีตัวประกอบเพียงสองตัว คือ 1 และตัวของมันเอง
จำนวนเฉพาะ
พิจารณาจำนวนเต็มบวก
1 ไม่เป็นจำนวนเฉพาะ เพราะมีตัวประกอบเพียงหนึ่งตัว คือ 1
2 เป็นจำนวนเฉพาะ เพราะมีตัวประกอบสองตัว คือ 1 กับ 2
3 เป็นจำนวนเฉพาะ เพราะมีตัวประกอบสองตัว คือ 1 กับ 3
4 ไม่เป็นจำนวนเฉพาะ เพราะมีตัวประกอบสามตัว คือ 1,2 และ 4
จะเห็นได้ว่า จำนวนเต็มบวกที่เป็นจำนวนเฉพาะ ยกเว้น 2 จะต้องเป็นจำนวนคี่
จำนวนเฉพาะที่ควรจำ ได้แก่ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 และ 37 จำนวนเฉพาะเหล่านี้ นักคณิตศาสตร์ชาวกรีก ได้คิดหาวิธีการให้ได้มาซึ่งจำนวนเฉพาะ โดยพบว่า
“เมื่อ 2 เป็นจำนวนเฉพาะตัวแรก นับจำนวนนับตัวต่อๆ ไปถ้าเพิ่มขึ้นอีก 2 จะเป็นจำนวนนับที่หารด้วย 2 ลงตัวทุกตัว จึงให้ตัดทิ้ง”
“จากนั้น 3 เป็นจำนวนเฉพาะ จึงนับจำนวนต่อไปทุก 3 ตัว จะเป็นจำนวนที่หารด้วย 3 ลงตัว จึงให้ตัดทิ้ง”
“จากนั้น 5 เป็นจำนวนเฉพาะ จึงนับจำนวนต่อไปทุก 5 ตัว จะเป็นจำนวนที่หารด้วย 5 ลงตัว จึงให้ตัดทิ้ง”
“7 ยังไม่ถูกตัด 7 เป็นจำนวนเฉพาะ นับจำนวนต่อไปครบ 7 เมื่อใดให้ตัดทิ้ง เพราะเป็นจำนวนที่หารด้วย 7 ลงตัว”
“ตัวเลขที่เหลือต่อไป คือ 11 เป็นจำนวนเฉพาะ นับจำนวนต่อไปครบ 11 ตัดทิ้ง”
กระทำในลักษณะเดียวกันไปเรื่อยๆจำนวนที่ไม่ถูกตัดคือ จำนวนเฉพาะ วิธีการนี้เรียกว่า ตะแกรงของเอราทอสเทนีส(Eratosthenes)
หลักการใช้ตะแกรงของเอราทอสเทนีส(Eratosthenes)
จำนวนเฉพาะระหว่าง 1 ถึง n ให้ใช้จำนวนเฉพาะทุกจำนวนที่เมื่อคูณกับตัวมันเอง แล้วผลคูณที่ได้ต้องไม่เกิน n มาเป็นตัวดำเนินการขีดฆ่าจำนวนอื่น
ร่อนหาจำนวนเฉพาะด้วย ตะแกรงของเอราทอสเทนีส(Eratosthenes)
เป็นวิธีหาจำนวนเฉพาะที่อยู่ระหว่าง 1 กับจำนวนนับที่กำหนดให้ โดยตัดจำนวนที่ไม่ใช่จำนวนเฉพาะทิ้ง
วิธีหาจำนวนเฉพาะ 1 ถึง 50 โดยใช้ตะแกรงของเอราทอสเทนีส(Eratosthenes)
เขียนจำนวนนับตามลำดับตั้งแต่ 1 ถึง 50 โดยเขียน 1 บรรทัดให้ได้ 10 จำนวน เพื่อความสะดวกและรวดเร็ว แล้วดำเนินตามขั้นตอนดังนี้
1) 1 ไม่ใช่จำนวนเฉพาะตัดทิ้ง
2) 2 เป็นจำนวนเฉพาะ วงไว้ ส่วนเลขคู่อื่นๆ(4,6,8,10,12, … )ให้ขีดฆ่าออกทุกตัว เนื่องจากไม่เป็นจำนวนเฉพาะ
3) 3 เป็นจำนวนเฉพาะ วงไว้ แล้วขีดฆ่าพหุคูณของ 3 หรือเรียกอีกอย่างหนึ่งว่า 3 หารเลขเหล่านั้นได้ลงตัว (6,9,12,15,18, …)ออกทั้งหมด
4) 5 เป็นจำนวนเฉพาะ วงไว้ แล้วขีดฆ่าพหุคูณของ 5 หรือเรียกอีกอย่างหนึ่งว่า 5 หารเลขเหล่านั้นได้ลงตัว (10,15,20,25,30, …)ออกทั้งหมด
5) 7 เป็นจำนวนเฉพาะ วงไว้ แล้วขีดฆ่าพหุคูณของ 7 หรือเรียกอีกอย่างหนึ่งว่า 7 หารเลขเหล่านั้นได้ลงตัว (14,21,28,35,42, …)ออกทั้งหมด
6) จากตารางจะพบจำนวนที่ไม่ถูกขีดฆ่า ดังต่อไปนี้
2, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 และ 47 ซึ่งเป็นจำนวนเฉพาะระหว่าง 1 ถึง 50
ข้อสังเกต ตามขั้นตอนการหาจำนวนเฉพาะโดยใช้ตะแกรงของเอราทอสเทนีส(Eratosthenes) ร่อนหาจำนวนเฉพาะเป็นไปตามหลักการที่กล่าวว่า จำนวนเฉพาะระหว่าง 1 ถึง n ให้ใช้จำนวนเฉพาะทุกจำนวนที่เมื่อคูณกับตัวมันเอง แล้วผลคูณที่ได้ต้องไม่เกิน n มาเป็นตัวดำเนินการขีดฆ่าจำนวนอื่นๆ จากจำนวนข้างต้น ในทีนี้ n = 50 จึงใช้เพียง 2, 3, 5 และ 7 ซึ่ง 7X 7 = 79 ไม่เกิน 50
หลักการตรวจสอบจำนวนเฉพาะ
ให้ n แทนจำนวนนับที่ต้องการตรวจสอบ
ขั้นที่ 1 หาจำนวนเฉพาะทุกจำนวนที่เมื่อคูณตัวเองแล้ว ผลคูณ ไม่เกิน n
ขั้นที่ 2 นำจำนวนเฉพาะที่ได้ในขั้นที่ 1ไปหาร n เพื่อดูว่าหารลงตัวหรือไม่ ถ้าไม่มีจำนวนเฉพาะจำนวนใดที่ได้ในขั้นที่ 1 หาร n ได้ลงตัว จะได้ว่า n เป็นจำนวนเฉพาะ แต่ถ้ามีจำนวนเฉพาะจำนวนหนึ่งจำนวนใดที่ได้ใน ขั้นที่ 1 หาร n ได้ลงตัวจะได้ว่า n ไม่เป็นจำนวนเฉพาะ
ตัวอย่างที่ 1 149 เป็นจำนวนเฉพาะหรือไม่
ขั้นที่ 1 หาจำนวนเฉพาะทุกจำนวนที่เมื่อคูณตัวเองแล้วผลคูณที่ได้ ไม่เกิน 149
ขั้นที่ 2 นำจำนวนเฉพาะที่ได้ในขั้นที่ 1 คือ 2, 3, 7 และ 11 ไปหาร 149 เพื่อดูว่าหารลงตัวหรือไม่
เนื่องจาก จำนวน ทั้ง ห้า จำนวนนี้ หาร 149 ไม่ลงตัว
ดังนั้น 149 เป็นจำนวนเฉพาะ
ตัวอย่างที่ 2 413 เป็นจำนวนเฉพาะหรือไม่
ขั้นที่ 1 หาจำนวนเฉพาะทุกจำนวนที่เมื่อคูณตัวเองแล้วผลคูณที่ได้ ไม่เกิน 413
ขั้นที่ 2 นำจำนวนเฉพาะที่ได้ในขั้นที่ 1 คือ 2, 3, 7, 11, 13, 17, และ 19 ไปหาร 413 เพื่อดูว่าหารลงตัวหรือไม่
เนื่องจาก 7 หาร 413 ลงตัว
ดังนั้น 413 ไม่เป็นจำนวนเฉพาะ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น