จำนวนเฉพาะ

นิยาม “จำนวนเฉพาะคือจำนวนเต็มบวกที่มีค่ามากกว่า 1 และมีเพียงเลข 1 กับตัวมันเองเท่านั้นที่หารตัวมันเองได้ลงตัว”

จำนวนเฉพาะเป็นสิ่งสำคัญทางด้านคณิตศาสตร์ ใช้กันมากในด้านการเข้า-ถอดรหัสด้วยคอมพิวเตอร์ จำนวนที่ไม่ใช้จำนวนเฉพาะเรียกว่าจำนวนประกอบ(ประกอบไปด้วยจำนวนเฉพาะ) การเรียงลำดับจำนวนเฉพาะตามนิยามจะเป็นดังนี้ 2, 3, 5, 7, 11, 13, ….

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

โปรแกรมคำนวนหาจำนวนเฉพาะ

main(){
int i,j,k,l;
printf(“Please your number : “);
scanf(“%d”,&j);
for(i=2;i<=j;i++){
for(k=2,l=0;k<i&&l==0;k++){
if(!(i%k)){l=1;}
}
if(l==0){
printf(“%dt”,i);
}
if(i==j&&l==0){
printf(“n***********************************n%d is primen***********************************nn”,j);
}else if(i==j&&l==1){
printf(“nnIt’n primen”);
}
}
}

โปรแกรมจะรับค่าจากผู้ใช้มาคำนวนว่าจำนวนที่ผู้ใช้กรอกมาเป็นจำนวนเฉพาะหรือไม่

สิ่งที่น่าสนใจ

– เลข 2 เป็นจำนวนคู่เพียงตัวเดียวที่เป็นจำนวนเฉพาะ (ดังนั้นถ้าเจอจำนวนคู่ที่ไม่ใช่ 2 จะไม่ใช่จำนวนเฉพาะทั้งหมด )
– เลขที่ลงท้ายด้วย 5 มีเพียงเลข 5 เท่านั้นที่เป็นจำนวนเฉพาะ (นอกนั้นเป็นจำนวนประกอบโดยมีเลข 5 เป็นตัวประกอบ)
– จำนวนอื่นที่ลงท้ายด้วย 0, 2, 4, 5, 6, 8, ไม่เป็นจำนวนเฉพาะ (จะมีเพียงเลข 5 และเลข 2 เท่านั้นที่เป็นจำนวนเฉพาะ)