Code kiểm tra số nguyên tố trong C/C++ và Java kèm giải thích

Phát biểu bài toán kiểm tra số nguyên tố: Cho một số nguyên x nhập từ bàn phím. Hãy kiểm tra xem số x có phải số nguyên tố hay không? Hãy cùng blog Nguyễn Văn Hiếu đi tìm đáp án nhé.

Khái niệm số nguyên tố

Số nguyên tố là số nguyên dương có duy nhất 2 ước phân biệt là 1 và chính nó. Lưu ý: Số 1 không phải số nguyên tố do chỉ có 1 ước.

Ý tưởng kiểm tra số nguyên tố

Nếu số đó bé hơn 2, kết luận không phải số nguyên tố.
Đếm số ước của x trong đoạn từ 2 đến căn bậc hai của x. Nếu số đó không có ước nào trong đoạn từ 2 đến căn bậc hai của x thì nó là số nguyên tố. Ngược lại thì không phải. Như vậy, nếu bạn đếm từ 1 thay vì 2 thì x là số nguyên tố khi ta đếm được 1 ước số trong đoạn từ 1 đến căn bậc hai của x.

Tại sao lại chỉ đếm các ước trong đoạn từ 2 đến căn của x?

Nếu bạn để ý thì một số nguyên >= 2 bất kỳ sẽ luôn có số ước ở nửa đầu căn bậc 2 của nó bằng số ước ở nửa sau căn bậc 2 của nó. Cụ thể, các ước sẽ phân bố thành 2 miền từ [2; sqrt(x)] và từ [sqrt(x); x].

Chú ý: Khi kiểm tra bạn nhớ phải là <= sqrt(n) nhé. Nếu chỉ để dấu nhỏ hơn thì các số chính phương như 4, 9 sẽ là số nguyên tố đấy. Tại sao thì bạn thử giải thích xem nào.

Ví dụ minh họa

Dành cho bạn: Tự học lập trình Winform C# qua 10 ứng dụng thực tế

Code minh họa thuật toán kiểm tra số nguyên tố

Sau đây mình sẽ triển khai code minh họa sử dụng C/C++, Java và Python cho các bạn. Các bạn nên tự thử trước khi xem lời giải. Không nên copy code =))

Kiểm tra số nguyên tố sử dụng C

Kiểm tra số nguyên tố sử dụng C++

Kiểm tra số nguyên tố sử dụng Java

Nếu bạn đang học cấu trúc dữ liệu và giải thuật, hãy xem ngay series các thuật toán sắp xếp sẽ giúp ích cho bạn đấy.

Xem thêm: