Bài 4. Bài toán và thuật toán tổ 1 10a4

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

- Nếu N ? 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N 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
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 ] 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ố, 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 ]
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.
D
S
S
D
S
S
D
D
Cách 2
Vẽ sơ đồ khối