เลขจำนวนจำเพาะ
 

                  (prime)

จากพจนานุกรม Webster ให้ความหมายของคำว่า Prime ไว้ดังนี้
 

 pprime \'prim\ n [ME, fr. MF, fem. of prin first, L primus; akin to L prior]
1 : first in time : ORIGINAL 2 a : having no factor except itself
and one <3 is a ~ number> b : having no common factor except
 one <12 and 25 are relatively ~> 3 a : first in rank, authority or
 significance : PRINCIPAL b : having the highest quality or
 value <~ television time> [Webster's New Collegiate Dictionary]

 
     ในที่นี้เน้นความหมายในเรื่องเลขจำนวนเฉพาะ ซึ่งเป็นตัวเลขที่มีลักษณะสมบัติน่าสนใจ และสามารถนำมาประยุกต์ใช้งานได้มากมาย

* เลขจำนวนเฉพาะ คือเลขจำนวนเต็มที่มีค่ามากกว่า 1 โดยตัวเลขนี้ไม่มีตัวเลขใดมาหารได้ลงตัว นอกจากตัวมันเอง และ หนึ่ง

   เลขจำนวนใด ๆ ที่เป็นจำนวนเต็มที่มีค่ามากกว่า 1 สามารถแยกตัวประกอบออกมาได้เป็นผลคูณของตัวเลขจำนวนเฉพาะเสมอ

ตัวอย่าง
                             1000 = 23.53  
                                             119 = 7.17
                                              997 = 997

จะหาเลขจำนวนเฉพาะได้อย่างไร

     ลองนึกดูว่าถ้าเรามีเลขจำนวนหนึ่ง คือ n โดยที่ n>1 และหากว่าเลข n นี้ประกอบด้วย ผลคูณของเลขจำนวนเฉพาะ a และ b หรือ n = ab โดยที่ a>1 และ 1 สิ่งที่เกิดขึ้นคือ ไม่ a หรือ b ตัวใดตัวหนึ่ง ต้องมีค่า < ด้วยหลักการง่าย ๆ อย่างนี้เอง เราสามารถนำมาใช้ในการหาเลขจำนวนเฉพาะ ตามที่เราต้องการได้

วิธีที่ 1

  
         การหาเลขจำนวนเฉพาะโดยทดลองหารด้วยจำนวนคี่ จนถึงค่ารากที่สองของจำนวนที่ต้องการหา
         การหาจำนวนเฉพาะทำได้ด้วยการนำตัวเลขมาหาร ซึ่งวิธีนี้เราจะเห็นได้ชัดว่า ตัวเลขคู่เป็นจำนวนเฉพาะมีเพียงตัวเดียว คือ 2
        จำนวนเฉพาะที่เหนือจาก 2 เป็นต้นไปจะต้องเป็นเลขคี่ แต่เลขคี่ทุกตัวไม่จำเป็นต้องเป็นจำนวนเฉพาะ
        วิธีการคือ ตัวเลขที่ต้องการดูว่าเป็นจำนวนเฉพาะหรือไม่ คือ n = 3, 5, 7, 9, 11, .....
       ให้ทำการทดลองหารด้วยจำนวนคี่ ที่มีค่า < และถ้าหารได้ไม่ลงตัวแสดงว่า n คือ จำนวนเฉพาะ
ตัวอย่างโปรแกรม

วิธีที่ 2
 
      การหาเลขจำนวนเฉพาะโดยทดลองหารด้วยเลขจำนวนเฉพาะที่มีค่าน้อยกว่าค่ารากที่สองของจำนวนที่ต้องการหา
       วิธีนี้คล้ายกับวิธีแรก แทนที่จะใช้จำนวนคี่ไปหารเพื่อทดสอบ ให้ได้เลขจำนวนเฉพาะไปทดลองหารดู ดังนั้นวิธีนี้จะต้องรู้ค่าเลขจำนวนเฉพาะที่มีค่าน้อยกว่า < แล้ว ซึ่งปกติการหาวิธีนี้จะไล่หาค่าจำนวนเฉพาะตัวก่อนหน้าไว้แล้ว โดยเก็บตัวเลขจำนวนเฉพาะที่หาได้ก่อนไว้ในที่เก็บ เช่น อะเรย์

ตัวอย่างโปรแกรม


 

ที่มา: รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์