จำนวนเฉพาะคือจำนวนที่หารด้วยตัวมันเองสองตัวและตัวหนึ่งเท่านั้น ตัวประกอบของตัวเลขคือตัวเลขที่หารได้
รายชื่อจำนวนเฉพาะสิบอันดับแรกคือ 2,3,5,7,11,13,17,23,29,31
จำนวนที่ไม่ใช่จำนวนเฉพาะคือจำนวนประกอบ จำนวนประกอบคือตัวเลขที่สามารถหารด้วยตัวเลขมากกว่าสองจำนวนได้
จากนั้น Elser เฉพาะไพรม์และคอมโพสิท จะมี 1 ตัวที่ไม่ใช่ไพร์มหรือคอมโพสิทเพราะแบ่งได้อย่างเดียวเท่านั้น
วิธีตรวจสอบว่าจำนวนใดเป็นจำนวนเฉพาะหรือประกอบเป็นจำนวนเฉพาะ มีสองเงื่อนไขที่ควรตรวจสอบ
1) ควรเป็นจำนวนเต็มที่มากกว่า 1
2) ควรมีตัวประกอบเพียง 2 ตัว คือ ตัวเดียวและตัวคูณ
หากทั้งสองเงื่อนไขเป็นไปตามเงื่อนไข เราก็บอกได้ว่าตัวเลขนั้นเป็นจำนวนเฉพาะ
ในโปรแกรมของเรา เราจะตรวจสอบการหารตัวเลขด้วยตัวเลขแต่ละตัวที่น้อยกว่าตัวเลขนั้น หากจำนวนใดที่น้อยกว่าจำนวนที่กำหนดมาหารกัน แสดงว่าไม่ใช่จำนวนเฉพาะ มิฉะนั้นจะเป็นจำนวนเฉพาะ
ลองมาดูตัวอย่างตัวเลขสองตัวและตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่โดยใช้กระบวนการนี้
Input − Number1 − 42 Output − 42 is not a prime number
ตรรกะ – เราจะหาร 42 ด้วยทุก ๆ จำนวนที่มากกว่า 1 และน้อยกว่า 42 ดังนั้น
42/2 =21 เช่น 42 หารด้วย 2 ลงตัว ซึ่งหมายความว่า 42 ไม่ใช่จำนวนเฉพาะเพราะหารด้วยจำนวนอื่นลงตัว
Input − Number2 − 7 Output − 7 is a prime number
ตรรกะ – เราจะหารเจ็ดด้วยทุก ๆ จำนวนที่มากกว่า 1 และน้อยกว่า 7 ดังนั้น
7 หารด้วย 2 ไม่ลงตัว ดังนั้นโค้ดจะตรวจสอบเลขถัดไป เช่น 3
7 หารด้วย 3 ไม่ลงตัว ดังนั้นโค้ดจะตรวจสอบเลขถัดไป เช่น 4
7 หารด้วย 4 ไม่ลงตัว ดังนั้นโค้ดจะตรวจสอบเลขถัดไป เช่น 5
7 หารด้วย 5 ไม่ลงตัว ดังนั้นโค้ดจะตรวจสอบเลขถัดไป เช่น 6
7 หารด้วย 6 ไม่ลงตัว ซึ่งหมายความว่า 7 หารด้วย 1 ลงตัวเพียง 1 และ 7 ลงตัวซึ่งหมายความว่า 7 เป็นจำนวนเฉพาะ
ดูตรรกะข้างต้นว่าตัวเลขจะเป็น 1,000 บวกหรือ 100000 บวกจากนั้นโปรแกรมจะวนซ้ำหลายครั้งสำหรับการวนซ้ำวิธีนี้จะใช้เวลาในการคำนวณมาก ดังนั้นหากต้องการลดจำนวนการทำซ้ำจะต้องเป็นวิธีที่ดีกว่า
ทางออกที่ดีที่สุดสำหรับสิ่งนี้คือการวนซ้ำครึ่งทางเท่านั้น ซึ่งหมายความว่าหากหมายเลขเป็น 77 การวนซ้ำจะทำงานจนถึง 38 เท่านั้น ซึ่งจะช่วยลดจำนวนการวนซ้ำที่จำเป็น ดังนั้นเราจะใช้อัลกอริทึมนี้เพื่อสร้างโปรแกรมของเรา
ตัวอย่าง
#include <stdio.h>
int main() {
int num = 33, flag = 0;
for(int i=2 ; i < num/2 ; i++) {
if(num%i == 0) {
printf("%d is not a prime number", num);
flag = 1;
break;
}
}
if(flag == 0) {
printf("%d is a prime number", num);
}
} ผลลัพธ์
33 is a prime number
