Sách giáo khoa Tin học 9

Giải Luyện tập trang 82 SGK Tin học 9

Bài 15. Bài toán tin học   Đã kiểm

Đề bài

Vẽ sơ đồ của thuật toán giải bài toán xác định một số có phải số nguyên tố hay không bằng cách chỉ sử dụng những cấu trúc điều khiển cơ bản.

Lời giải

## Thuật toán kiểm tra một số có phải số nguyên tố hay không

### 1. Phân tích bài toán

- Đầu vào (Input): một số tự nhiên nn.
- Đầu ra (Output): kết luận "nn là số nguyên tố" hoặc "nn không phải số nguyên tố".

### 2. Ý tưởng thuật toán

Theo định nghĩa, nn là số nguyên tố khi nn là số tự nhiên lớn hơn 11 và chỉ có đúng hai ước là 11 và chính nó. Do đó ta kiểm tra như sau:

1. Nếu n<2n < 2 thì nn không phải số nguyên tố.
2. Nếu n≥2n \ge 2: lần lượt thử các số i=2,3,…,n−1i = 2, 3, \dots, n-1 để xem có số nào là ước của nn hay không (tức n mod i=0n \bmod i = 0).
- Nếu tìm được một ước như vậy thì nn có ước khác 11 và chính nó ⇒\Rightarrow nn không phải số nguyên tố.
- Nếu thử hết mà không có ước nào thì nn là số nguyên tố.

Thuật toán chỉ dùng ba cấu trúc điều khiển cơ bản đã học: tuần tự, rẽ nhánh và lặp.

### 3. Sơ đồ khối (sơ đồ thuật toán)

*Quy ước: hình ô van = Bắt đầu/Kết thúc; hình bình hành = Nhập/Xuất; hình chữ nhật = Thực hiện phép tính; hình thoi = Điều kiện (rẽ nhánh).*

```
┌─────────────┐
│ Bắt đầu │ (ô van)
└──────┬──────┘
│
┌──────▼──────┐
│ Nhập n │ (bình hành)
└──────┬──────┘
│
╱────▼────╲
╱ n < 2 ? ╲──── Đúng ───────────────┐
╲ ╱ │
╲────┬────╱ │
│ Sai │
┌──────▼──────┐ │
│ i ← 2 │ │
└──────┬──────┘ │
│ │
┌───────▼───────┐ │
┌─▶│ i < n ? │──── Sai ──────────────────────┐
│ └───────┬───────┘ │ │
│ │ Đúng │ │
│ ╱────▼─────╲ │ │
│ ╱ n mod i=0? ╲──── Đúng ────────────────┤ │
│ ╲ ╱ │ │
│ ╲────┬─────╱ │ │
│ │ Sai ▼ ▼
│ ┌───────▼───────┐ ┌──────────────┐ ┌──────────────┐
└──│ i ← i + 1 │ │ Thông báo: │ │ Thông báo: │
└───────────────┘ │ n KHÔNG phải │ │ n là số │
│ số nguyên tố │ │ nguyên tố │
└──────┬───────┘ └──────┬───────┘
└────────┬───────┘
┌─────▼─────┐
│ Kết thúc │ (ô van)
└───────────┘
```

### 4. Giải thích luồng điều khiển

- Tuần tự: các khối *Nhập n* →\rightarrow *i←2i \leftarrow 2* được thực hiện lần lượt.
- Rẽ nhánh: hai khối điều kiện hình thoi *"n<2n < 2 ?"* và *"n mod i=0n \bmod i = 0 ?"* cho phép chương trình đi theo nhánh Đúng hoặc Sai.
- Lặp: khối điều kiện *"i<ni < n ?"* cùng khối *i←i+1i \leftarrow i + 1* tạo thành vòng lặp: mỗi lần lặp thử một ước ii; biến ii tăng dần cho tới khi i=ni = n thì dừng.

### 5. Kiểm tra lại bằng ví dụ

- n=1n = 1: điều kiện n<2n < 2 Đúng →\rightarrow *không phải số nguyên tố* (đúng).
- n=2n = 2: n<2n < 2 Sai, i←2i \leftarrow 2, i<ni < n (2<22 < 2) Sai →\rightarrow *là số nguyên tố* (đúng).
- n=7n = 7: ii lần lượt là 2,3,4,5,62, 3, 4, 5, 6 đều cho 7 mod i≠07 \bmod i \ne 0; khi i=7i = 7 thì i<ni < n Sai →\rightarrow *là số nguyên tố* (đúng).
- n=9n = 9: với i=3i = 3 có 9 mod 3=09 \bmod 3 = 0 Đúng →\rightarrow *không phải số nguyên tố* (đúng).

Sơ đồ hoạt động chính xác.

Đáp số

Sơ đồ khối thuật toán kiểm tra số nguyên tố dùng 3 cấu trúc cơ bản: tuần tự (nhập n, i ← 2, i ← i+1) – rẽ nhánh ("n < 2?", "n mod i = 0?") – lặp ("i < n?" với i tăng dần từ 2 đến n-1)

Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.