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.
- Share CrocoBlock key trọn đời Download Crocoblock Free
- Cung cấp tài khoản nghe nhạc đỉnh cao Tidal Hifi – chất lượng âm thanh Master cho anh em mê nhạc.
- Tải nhanh hack thần tướng – epic heroes war full kim cương auto thành công 100% mới nhất 2021 – Tinh dầu LATIMA
- iPhone 11 64GB 2 Sim vật lý giá rẻ, Quốc tế – Bán trả góp 0%
- Có nên dùng tool chém giá Lazada để sở hữu sản phẩm 0đ?
- ̂ ́ ♀️
- Mách bạn những cách khắc phục khi Laptop không có bluetooth