Tiet 11

Thuật toán kiểm tra tính nguyên tố của một số nguyên dương
Xác định bài toán:
INPUT: N là một số nguyên dương.
OUTPUT: Trả lời câu hỏi N có là số nguyên tố không ?
ý tưởng: Xét các trường hợp

Các em hãy nêu định nghĩa số nguyên tố.
- Nếu N ? 4 và không có ước số trong phạm vi từ 2 đến (N - 1) thì N là số nguyên tố.
- Nếu N = 1 thì N không là số nguyên tố.

- Nếu 1< N <4 thì n là số nguyên tố.

45 không là số nguyên tố.
29 là số nguyên tố.
Mô phỏng thuật toán kiểm tra tính nguyên tố
Cách 1: Liệt kê các bước
B1: Nhập số nguyên dương N;
B2: Nếu N = 1 thông báo N không nguyên tố, kết thúc;
B3: Nếu N < 4 thông báo N là nguyên tố rồi kết thúc;
B4: i ?2;
B5: Nếu i > [ N-1 ] thì thông báo N là nguyên tố, kết thúc;
B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;
B7: i ? i +1 rồi quay lại B5.
Nhập N
N =1 ?
N < 4 ?
i ? 2
i>[N-1] ?
N có chia hết cho i ?
i ? i +1
Thông báo N là số nguyên tố rồi kết thúc.
Thông báo N không là số nguyên tố rồi kết thúc.
Đ
S
S
Đ
S
S
Đ
Đ
Cách 2
Vẽ sơ đồ khối