ชุดที่ 2 จำนวนเฉพาะ

จำนวนเฉพาะ คือ จำนวนเต็มบวกที่มากกว่า 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)

7

หลักการใช้ตะแกรงของเอราทอสเทนีส(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

8

ข้อสังเกต  ตามขั้นตอนการหาจำนวนเฉพาะโดยใช้ตะแกรงของเอราทอสเทนีส(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 ไม่เป็นจำนวนเฉพาะ