Lời giải chi tiết

Ý tưởng: Duyệt các giá trị \(i\) từ 2 tới \(a\). Nếu \(i\) là số nguyên tố thì ta sẽ cộng biến đếm số nguyên tố thêm 1. Sau đó khi duyệt đến số \(a\) mà \(a\) không phải số nguyên tố thì in ra NO. Ngược lại thì in ra YES và giá trị biến đếm ta có được cộng thêm 1.

Các bước giải:

• Bước 1: Khai báo và nhập vào số \(q\) thể hiện số truy vấn, sau đó chạy truy vấn.
• Bước 2: Khai báo và nhập vào số \(a\). Sau đó khởi tạo một biến count biểu thị số lần đếm được số nguyên tố và gán giá trị khởi tạo là 0. Sau đó ta kiểm tra điều kiện: trong trường hợp nếu \(a < 2\) thì ngay lập tức in ra NO và tiếp tục với truy vấn tiếp theo. Còn nếu \(a \geq 2\) ta tiếp tục với bước 3.
• Bước 3: Sử dụng vòng lặp để duyệt \(i\) từ 2 đến \(a\). Với mỗi giá trị \(i\), kiểm tra xem \(i\) có phải số nguyên tố hay không. Với mỗi lần tìm được nguyên tố \(i\), ta sẽ tăng count thêm 1.
• Lưu ý: Để kiểm tra được \(i\) có là số nguyên tố hay không, ta sẽ duyệt tất cả các số từ 2 đến \(i - 1\) và kiểm tra từng số xem chúng có chia hết cho \(i\) hay không. Nếu tồn tại 1 số chia hết cho \(i\) thì \(i\) không phải số nguyên tố. Ngược lại, nếu \(i\) không có số nào chia hết ngoại trừ 1 và chính nó thì \(i\) là số nguyên tố. Phương pháp này có thể được cải tiến bằng thay vị duyệt từ 2 đến \(i\), ta chỉ cần duyệt từ 2 đến \(\sqrt{i}\), vì nếu \(i\) có 1 ước là \(j\), thì nó cũng sẽ có một ước khác là \(\frac{j}{i}\). Ta còn có thể cải tiến lên tối ưu hơn bằng cách check \(i\) có chia hết cho 2 hay không, nếu không thì ta sẽ duyệt các số lẻ từ 3 đến \(\sqrt{i}\) thay vì duyệt từ \(2\) đến \(\sqrt{i}\).
• Bước 4: Sau khi duyệt xong số cuối cùng, tức số \(a\), nếu ta kiểm tra được \(a\) là số nguyên tố, in ra màn hình YES và giá trị cuối cùng của count, cách nhau 1 dấu cách. Ngược lại, nếu \(a\) không là số nguyên tố thì in ra NO.
• Bước 5: Xuống dòng để tiếp tục với các truy vấn sau đó.

Đăng ký khóa học: https://www.facebook.com/clblaptrinhfullhouse

SĐT liên hệ: 0372229686

Youtube: CLB Lập Trình Full House

Fullhouse dev đồng hành trên từng dòng code