Dùng phương pháp mịn dần để giải. Đầy đủ các bước như sách đã chỉ

### 1. Giải bài toán kiểm tra số nguyên tố bằng phương pháp làm mịn dần **Bước 1: Hiểu bài toán** - Đầu vào: Một số tự nhiên không âm $$. - Đầu ra: Thông báo "CÓ" nếu $$ là số nguyên tố, ngược lại thông báo "KHÔNG". **Bước 2: Định nghĩa số nguyên tố** - Số nguyên tố là số tự nhiên lớn hơn 1 chỉ chia hết cho 1 và chính nó. **Bước 3: Xây dựng thuật toán** 1. Nếu $$, in ra "KHÔNG". 2. Duyệt từ $$ đến $$: - Nếu $$ chia hết cho bất kỳ số nào trong khoảng này, in ra "KHÔNG". 3. Nếu không tìm thấy số nào chia hết, in ra "CÓ". **Bước 4: Viết chương trình** ```python def kiem_tra_so_nguyen_to(n): if n < 2: return "KHÔNG" for i in range(2, int(n**0.5) + 1): if n % i == 0: return "KHÔNG" return "CÓ" # Ví dụ sử dụng n = int(input("Nhập số tự nhiên không âm n: ")) print(kiem_tra_so_nguyen_to(n)) ``` ### 2. Chứng minh thuật toán sắp xếp chèn **Bước 1: Hiểu thuật toán sắp xếp chèn** - Thuật toán sắp xếp chèn (Insertion Sort) hoạt động bằng cách chia mảng thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Mỗi lần, nó lấy một phần tử từ phần chưa sắp xếp và chèn vào vị trí đúng trong phần đã sắp xếp. **Bước 2: Thay thế phần chèn** - Thay thế phần chèn $$ vào vị trí đúng của dãy con $$ bằng các lệnh sau: 1. $$ 2. Trong khi $$ và $$: - Đổi chỗ $$ và $$ - $$ **Bước 3: Chứng minh** - Khi $$, $$ là phần tử cần chèn. - Vòng lặp sẽ tiếp tục cho đến khi tìm thấy vị trí đúng cho $$ trong dãy đã sắp xếp. - Nếu $$, điều này có nghĩa là $$ cần phải được di chuyển về phía trước. - Việc đổi chỗ $$ và $$ đảm bảo rằng dãy con vẫn được sắp xếp sau mỗi lần đổi chỗ. - Khi vòng lặp kết thúc, $$ sẽ được đặt vào vị trí đúng trong dãy đã sắp xếp, và dãy vẫn giữ nguyên tính chất đã sắp xếp. **Kết luận** - Việc thay thế này không làm thay đổi tính đúng đắn của thuật toán sắp xếp chèn, vì nó vẫn đảm bảo rằng dãy con $$ sẽ được sắp xếp đúng sau khi thực hiện các lệnh trên.