Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Để kiểm tra một số n có nguyên tố không, ta chỉ cần thử các ước đến $\sqrt{n}$ — vì nếu n có ước lớn hơn căn thì cũng có ước nhỏ hơn căn tương ứng:

bool nguyenTo(int n) {
    if (n < 2) return false;
    for (int i = 2; (long long)i * i <= n; i++) {  // chi den can(n)
        if (n % i == 0) return false;              // co uoc -> khong nguyen to
    }
    return true;
}

Kiểm tra từng số đến $\sqrt{n}$ tốn $O(\sqrt{n})$. Nhưng nếu cần biết mọi số nguyên tố trong khoảng 1..N, có cách nhanh hơn nhiều: sàng Eratosthenes.