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.

Author: buitrunghieu

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 ra YES.
  • 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

There are no comments at the moment.

Zalo