Bài tập về số nguyên tố ôn thi HSG Pascal – Có hướng dẫn

Xin giới thiệu với các bạn một loạt các bài tập liên quan đến số nguyên tố để ôn thi HSG pascal, các bạn hãy cố gắng luyện tập để giải hết các bài tập này để khi gặp đúng dạng có thể bắt tay vào thực hiện ngay mà không cần phải suy nghĩ nhiều.

Bài tập 1: Kiểm tra số nguyên tố

Viết chương trình nhập vào một số từ bàn phím (hoặc từ file) một số n (n < 2 tỉ) . Kiểm tra xem n có phải là số nguyên tố không? nếu phải thì xuất ra “Yes” nếu không phải xuất ra “No”

Code mẫu bằng pascal

Trên đây là chương trình kiểm tra số nguyên tố viết theo cách sử dụng chương trình con các bạn cần nắm vững chương trình con này để có thể mở rộng giải quyết những bài tập liên quan

Bài tập 2: Đếm và tính tổng các số nguyên tố

Lập trình nhập vào một số n, xuất ra những số nguyên tố nhỏ hơn hoặc bằng n. Đếm và tính tổng của tất cả những số nguyên tố đó.

Gợi ý: Để giải quyết bài toán trên các bạn nên:

  • Viết chương trình con kiểm tra một số có phải là số nguyên tố không (Tham khảo code bài tập 1)
  • Cho i chạy từ 1 đến n kiểm tra xem i có phải là số nguyên tố không, nếu phải thì đếm và tính tổng. Ở đây đếm và tính tổng đều sử dụng kỹ thuật cộng dồn để thực hiện

Bài tập 3: Phân tích ra thừa số nguyên tố

Viết chương trình phân tích một số tự nhiên n (n <2 tỉ) ra thừa số nguyên tố.

VD: Nhập vào n = 60 kết quả: 60 = 2.2.3.5

Gợi ý: Bạn cũng phải viết một chương trình con kiểm tra số nguyên tố nhé sau đó khéo léo lập trình để tách dần số đó thành tích của các số nguyên tố, trong quá trình tách chắc chắn các bạn phải dùng hàm Mod để kiểm tra tính chia hết. Mình đưa ra một đoạn mã để các bạn tham khảo

Bài tập 4: Tỉa số nguyên tố

Viết chương trình nhập vào một mảng n phần tử là các số nguyên không quá 2 tỉ (n <1000). Yêu cầu tỉa bỏ các số nguyên tố có trong mảng đó và xuất kết quả ra.

(Có thể nhập xuất từ bàn phím hoặc file)

Gợi ý: Bài này có nhiều cách giải quyết

Cách 1: Bạn duyệt từ đầu đến hết mảng khi nào gặp số nguyên tố thì loại nó ra bằng cách đầy các phần tử sau nó lên.

Cách 2: Dùng kĩ thuật mảng đánh dấu để đánh dấu những số là số nguyên tố sau đó xuất ra những phần tử chưa được đánh dấu.

Mình thích cách làm số 2 vì đơn giản dễ hiểu, còn tùy bạn lựa chọn.

Vậy là mình đã đưa ra 4 bài tập cơ bản về số nguyên tố, mình sẽ tiếp tục cập nhật thêm các bài mới, bạn nào có bài tập nào hay xin vui lòng chia sẻ bằng cách comment bên dưới để cùng chia sẻ với các bạn.

Share this post:

Related Posts

Leave a Comment