Editorial for C Bài 3.C1: Số lẻ nguyên tố
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Lời giải chi tiết
Ý tưởng: Ta chia cho đến khi \(a\) là số lẻ hoặc bằng 2 thì dừng lại, sau đó duyệt từ 3 đến \(a - 1\) kiểm tra xem có số nào chia hết cho \(a\) mới hay không. Cải tiến: ta có thể duyệt từ 3 đến \(\sqrt{a}\) do \(a\) luôn có 2 ước dưới dạng \(i\) và \(\frac{a}{i}\)(nếu \(i = \sqrt{a}\) thì \(i = \frac{a}{i}\)).
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, sử dụng while để chạy mỗi truy vấn.
- Bước 2: Khai báo và nhập vào số \(a\). Sau đó chia nó cho 2 cho đến khi \(a\) là số lẻ hoặc bằng 2 thì dừng.
- Bước 3: Sử dụng vòng lặp để duyệt các số, kiểm tra xem ngoài \(1\) và \(a\) mới ra, \(a\) có chia hết cho các số được duyệt hay không. Nếu gặp một số chia hết thì in ra
NO
và kết thúc vòng lặp. Nếu duyệt hết mà không có vấn đề thì in raYES
. - Bước 4: 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
Comments