จำนวนเฉพาะ (Prime) = จำนวนเต็ม > 1 ที่หารได้แค่ 1 และตัวเอง: 2, 3, 5, 7, 11, 13, 17...
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
void isPrime(int n) {
int i, flag = 0;
for(i=2; i<=n/2; ++i) {
if(n%i == 0) {
flag = 1;
break;
}
}
if (flag == 0)
cout << n << " is a prime number" << endl;
else
cout << n << " is not a prime number" << endl;
}
int main() {
isPrime(17);
isPrime(20);
return 0;
}
ผลลัพธ์
17 is a prime number 20 is not a prime number
อธิบายอัลกอริทึม
isPrime(n) ตรวจสอบ n ว่าเป็นเฉพาะหรือไม่:
for(i=2; i<=n/2; ++i) {
if(n%i == 0) {
flag = 1;
break;
}
}
- วน i = 2 ถึง n/2 (เพราะตัวหารมากกว่า n/2 ไม่สามารถหาร n ลงตัวได้)
- ถ้า n%i == 0 → หารลงตัว → ไม่ใช่เฉพาะ flag=1 break
- จบ loop flag=0 → เป็นเฉพาะ
main() เรียก isPrime(17) และ isPrime(20)
