จากพจนานุกรม 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 สามารถแยกตัวประกอบออกมาได้เป็นผลคูณของตัวเลขจำนวนเฉพาะเสมอ

ตัวอย่าง


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

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

วิธีที่ 2

 
การหาเลขจำนวนเฉพาะโดยทดลองหารด้วยเลขจำนวนเฉพาะที่มีค่าน้อยกว่าค่ารากที่สองของจำนวนที่ต้องการหา

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

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