โปรแกรม C++ ตรวจสอบจำนวนเฉพาะ (Prime Number)

จำนวนเฉพาะ (Prime Number) คือ จำนวนเต็มที่มากกว่า 1 และมีตัวหารได้เพียง 1 และตัวมันเอง

จำนวนเฉพาะแรกๆ: 2, 3, 5, 7, 11, 13, 17...

โปรแกรมตรวจสอบจำนวนเฉพาะ

#include <iostream>
using namespace std;

int main() {
    int n = 17, 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";
    else
        cout << n << " is not a prime number";
    return 0;
}

ผลลัพธ์

17 is a prime number

ตรรกะ: ลูปวนจาก 2 ถึง n/2 (เพราะตัวหารมากที่สุดที่เป็นไปได้ของ n คือ n/2) หาก n หารด้วย i ใดๆ ลงตัว (n % i == 0) แสดงว่าไม่ใช่จำนวนเฉพาะ ตั้ง flag = 1 และออกจากลูปด้วย break

หมายเหตุเพิ่มเติม: สามารถเพิ่มประสิทธิภาพได้โดยวนจนถึง sqrt(n) แทน n/2