Chương trình C++ kiểm tra số nguyên tố

Số nguyên tố là số nguyên lớn hơn 1 và chỉ có ước là 1 và chính nó. Các số nguyên tố đầu tiên: 2, 3, 5, 7, 11, 13, 17.

Chương trình kiểm tra số nguyên tố:

Ví dụ

#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;
}

Đầu ra

17 is a prime number

Vòng lặp chạy từ 2 đến n/2. Mỗi giá trị chia n. Nếu dư 0, n chia hết cho số khác 1 và chính nó -> không phải nguyên tố, đặt flag=1 và thoát vòng lặp.

for (i = 2; i <= n / 2; ++i) {
    if (n % i == 0) {
        flag = 1;
        break;
    }
}

Nếu flag vẫn 0 -> số nguyên tố. Nếu flag thành 1 -> không phải số nguyên tố.