Thuật toán tìm số nguyên tố trong C++

Số nguyên tố là số chỉ chia hết cho 1 và chính nó.

Ví dụ: số 7 là số nguyên tố nhưng số 9 không phải là số nguyên tố. Vì số 7 chỉ chia hết cho 1 và 7, nhưng số 9 lại có thể chia hết cho 3, nên 9 không phải là số nguyên tố.

Thuật toán kiểm tra như sau:

• có số n cần kiểm tra,
• ta sẽ lần lượt lấy n chia cho các số từ 2 -> căn bậc 2 của n, 
• chỉ cần n chia hết cho 1 trong các số từ 2-> căn bậc 2 của n thì n không phải là số nguyên tố, ngược lại n là số nguyên tố

Video hướng dẫn: